最近做的BZOJ题目 I

VictorWonder posted @ 2014年12月25日 19:39 in BZOJ with tags 刷题记录 , 938 阅读

因为有一些题目难度不是很大,网上也能够搜到题解,单独拿出来讲也没有什么意思,所以就在这里稍稍记录一下,不另写博文了,而且,从标题可以看出来,这将会是一系列的博文。

36

Updata:这里一共记录了36道题目的简单题解,感觉也差不多了,而且,36是个好数字,我就不破坏它了。所以这一篇到这里就结束吧,敬请期待Ⅱ。

BZOJ 1191 二分图匹配水题,匈牙利算法直接过。

BZOJ 2326 矩阵乘法+数学分类讨论。

BZOJ 1271 二分答案。

BZOJ 1196 这题以前用贪心水过,直到今天才发现,我的贪心是有问题的,是可以被卡掉的,这题应该二分答案。

BZOJ 1211 和明明的烦恼差不多,只是需要分解质因数,否则乘起来会爆掉long long。本来想打python的,后来发现似乎有点麻烦……

BZOJ 3674 这题是3673的加强版,3673的骗分办法就懒得讲了,随便YY一下就可以了。而且,反正只要把这题AC了,3673也就顺便AC了(双倍经验),用主席树维护可持久化数组,结果出了问题,但是自己电脑上怎么也拍不出来,后来照着Claris的程序改,发现是因为路径压缩的时候,直接在树上的节点上改了,没有另外地用change()改一下,结果就是,改了的结点可能是很久以前某次操作后留下来的结点……

BZOJ 1257 我最讨厌的数学题,不过这道题目也算是简单的了,并非数论神题。首先,通过打表可以发现,对于一个i,当[tex]t=\frac{n}{i} \rightarrow (\frac{n}{i+1} +1)[/tex]时,n%t的值都是递增的,根据这个规律,所有小于[tex]\sqrt{n}[/tex]的数都可以暴力求出n%i,接着再对于[tex]i=1 \rightarrow \sqrt{n}[/tex]用等差数列求和的办法求出,要注意的是必须要long long,还有一些细节对拍一下就行了。

BZOJ 2729 组合数学题,有点坑。开始的时候直接插空法,一直都AC不了,"98 2"的数据就将我的程序卡掉了,后来才明白有一种特殊情况没有考虑、假设,男生先全都站好,那么就有n!种站法,接着将两个老师插入进去,有A(n+1,2)种站法,最后将女生们插入进去,有A(n+3,m)种站法,乘起来就是答案,但是,这种考虑忽略了一种情况,两个老师可能是被女生给隔开的,也就是说,两个老师可以站在一起,在将女生插入进去的时候,有一个女生将老师给隔开了(因为两个女生不能相邻,所以将老师隔开的只能是一个女生),这样就有m*2种站法(老师的先后位置也要考虑),然后再将这个当成一组,插入到男生中,最后再将剩余的女生插入到队伍中。总的答案=n!*(A(n+1,2)*A(n+3,m)+m*2*(n+1)*A(n+2,m-1))。懒得打高精度了,直接用了python。

BZOJ 1858 线段树水题,结果还是调了很久TAT,不过样例过了就一遍AC了。

BZOJ 1059 二分图匹配,因为扒了模板,所以有些冗长。

BZOJ 3083 树链剖分+线段树+dfs序,开始的时候假设1为根dfs并建树。真实的根可能会发生变化,所以需要考虑根所在的位置,如果根在查询的结点x的子树中,则找到根到x路径上离x最近的那个结点y,查询的时候就查询整棵树中除了y的子树的那一部分;当根不再x的子树中时,就直接查询x的子树。

BZOJ 1412 最小割,源点往狼连边,容量无限,羊往汇点连边,容量无限,狼往所有非狼格子连边,容量为1,空地往所有非狼连边,容量为1。很久以前在vijos上做过,结果由于莫名其妙的原因,一直没有AC……

BZOJ 1067 离散化+线段树,要考虑的情况比较多,所以就不一一罗列了,具体的可以看程序,其次,这道题目在vijos上也是有的,但是,如果对于x==y的情况(虽然题面上说保证这种数据不存在)不考虑的话,会各种WA的,而且,如果x==y时,当年的降雨量不知道,必须要输出maybe而不能输出true……

BZOJ 3155 本题BZOJ上的题面是错误的,大致的题意是这样的,设Si一个数列a1,a2,...an前i个数的和,那么对于给定的数列{an},就会有一个对应的数列{Sn},现在需要进行两种操作:1.修改ai的值为x 2.查询{Sn}中前i个数的和。树状数组维护一下就行了,很简单。

BZOJ 3064 线段树区间更新,要打四个标记,分类讨论一下就行了。还有,刚发现我的读优模板出了个小错误,读负数的时候会有点问题,不过之前的程序都懒得改了,大家注意一下。

BZOJ 1911 斜率优化DP。果然,DP永远都是我的弱项,虽然一眼就看出来是斜率优化DP,但是,还是卡了好久,于是上网搜了一篇有关斜率优化的文章,结果发现自己公式化简的时候完全搞错了TAT……

BZOJ 1024 直接暴搜就行了

BZOJ 1029 贪心,开始的时候还以为是DP,结果推到死都推不出结果来,后来去百度了一下题解才知道原来是贪心,果然我还是太弱了吗……

BZOJ 1096 斜率优化DP,开始的时候以为是简单的单调队列优化DP,结果怎么调都调不出来,然后Claris一语道破天机,我才知道是斜率优化DP,稍稍推了一下公式就做出来了

BZOJ 1207 特殊版的LIS,还是[tex]O(n^2)[/tex]的,不过还是卡过去了。

BZOJ 1452 二维树状数组,本来打的是二维线段树,结果MLE,把数组开小一点后RE了,然后以为二维线段树不可做就改打了二维树状数组,结果也各种RE,后来才发现原来主程序的一个地方打错了……

BZOJ 1922 有特殊要求的最短路,按照题目要求搞就好了,开始的时候打了Dijkstra,结果怎么也调不出来……后来改打SPFA,也怎么也调不出来……直到最后,我才看到题目里面说,所有边都是单向边……

BZOJ 1968 数学题,开始的时候还打了筛法,在自己电脑上是过去了,BZ上也卡过去了(BZ上这题的时间限制竟然只有1s),后来才知道原来根本不用求素数,直接暴力就行了……

BZOJ 2818 也是数学题,先线性筛求出[tex]\varphi(x)[/tex]函数,然后枚举每个素数就行了。

BZOJ 1045 想了好久,最后YY出了一种错误的做法,算出来的值比答案要小。然后就直接去网上搜题解了,后面是我看的题解的链接:http://www.cnblogs.com/JS-Shining/archive/2012/09/24/2700711.html

BZOJ 1821 二分答案+并查集。

BZOJ 2190 欧拉函数。忽然发现,我的欧拉函数的模板好像不是线性筛的,而是爱氏筛,线性筛都不会打了……不过暂时也懒得回顾了,就先这样吧。

BZOJ 2631 LCT裸题,不知道为什么,这一次的LCT打的特别萎,速度很慢,好在还是跑出来了。

BZOJ 2243 树链剖分。

BZOJ 1854 二分图匹配,和HNOI的那道超级英雄差不多,唯一要注意的是,数据比较大,所以跑匈牙利算法的时候要用时间戳,不然会超时。

BZOJ 1037 四维DP。开始以为是三维DP,结果连样例都过不了,后来转成四维DP,因为状态出了问题,本来打算f[i][j][k][l]表示前i位,有j个男孩纸,右端点为i的某一段中,男孩纸和女孩纸数目之差为k(所以会有负数),最后一共有连续l个相同的孩纸(l为正表示男孩纸,为负表示女孩纸),结果惨遭WA,而且,MLE了(开了两亿多数组,在BZOJ 上Compiling了一分钟左右,话说我真得不是故意的)后来才发现这样搞不好,然后去网上搜了一下,变成了右端点为i的某段中男孩纸最多比女孩纸多了k个,女孩纸最多比男孩纸多了l个,然后稍稍改一下转移方程就AC了。

BZOJ 1877 拆点费用流,结果TLE了好久,后来胡乱地将源点s和汇点t的变量名从小写改成大写然后就AC了……

BZOJ 1103 树链剖分。

BZOJ 1216 我果然还是太弱了,这么水的模拟题都做了这么久,一直出错,直到今天头脑稍稍清醒了一点,终于做出来了。

BZOJ 1293 离散化后再扫一遍就行了。

BZOJ 3824 简单的状压DP。

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=10010;
int n,m,belong[N];
int g[N],to[N],nxt[N],tot;
bool v[N];
void addedge(int x,int y) {
    to[++tot]=y; nxt[tot]=g[x]; g[x]=tot;
}
bool match(int x) {
    for (int k=g[x];k;k=nxt[k]) {
        if (v[to[k]]) continue;
        v[to[k]]=true;
        if (!belong[to[k]]||match(belong[to[k]])) {
            belong[to[k]]=x;
            return 1;
        }
    }
    return 0;
}
int main() {
    int i,x,y;
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;i++) {
        scanf("%d%d",&x,&y);
        addedge(i,x);
        addedge(i,y);
    }
    for (i=1;i<=n;i++) {
        memset(v,0,sizeof(v));
        if (!match(i)) break;
    }
    printf("%d\n",i-1);
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const D eps=1e-6;
const D pi=acos(-1.0);
int mod;
ll n,ans,t[30],r[30];
ll g[5][5],f[5],e[5],h[5][5];
void power1() {
    int i,j,k;
    for (i=1;i<=3;i++) for (j=1;j<=3;j++) h[i][j]=0;
    for (k=1;k<=3;k++) for (i=1;i<=3;i++) for (j=1;j<=3;j++) (h[i][j]+=(g[i][k]*g[k][j])%mod)%=mod;
    for (i=1;i<=3;i++) for (j=1;j<=3;j++) g[i][j]=h[i][j];
}
void power2() {
    int i,j;
    for (i=1;i<=3;i++) e[i]=0;
    for (i=1;i<=3;i++) for (j=1;j<=3;j++) (e[i]+=(g[i][j]*f[j])%mod)%=mod;
    for (i=1;i<=3;i++) f[i]=e[i];
}
ll calc(ll x,int y,ll b) {
    f[1]=x; f[2]=(r[y]-1)%mod; f[3]=1;
    g[1][1]=r[y+1]%mod; g[1][2]=1; g[1][3]=1;
    g[2][1]=0; g[2][2]=1; g[2][3]=1;
    g[3][1]=g[3][2]=0; g[3][3]=1;
    for (;b;b>>=1LL) {
        if (b&1LL) power2();
        power1();
    }
    return f[1]%mod;
}
int main() {
    int i;
    cin>>n>>mod;
    for (t[0]=9,i=1;i<=18;i++) t[i]=t[i-1]*10;
    for (r[0]=1,i=1;i<=18;i++) r[i]=r[i-1]*10;
    for (i=0;i<18;i++) {
        if (t[i]<=n) {
            ans=calc(ans,i,t[i]);
            n-=t[i];
        } else {
            ans=calc(ans,i,n);
            break;
        }
    }
    cout<<ans<<endl;
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=200010;
struct node{int l,r,d;}b[N];
int T,n,sum,ans;
void read(int &a) {
    char ch; while (!((ch=getchar())>='0'&&ch<='9'));
    a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
bool check(int l,int r) {
    sum=0; int i,t;
    for (i=1;i<=n;i++) {
        if (b[i].r<l||b[i].l>r) continue;
        sum+=(min(b[i].r,r)-b[i].l)/b[i].d+1;
        if (b[i].l<l) sum-=(l-b[i].l-1)/b[i].d+1;
    } return sum&1;
}
int solve(int l,int r) {
    if (l==r) return check(l,r)?l:-1;
    int mid=((ll)l+(ll)r)>>1ll;
    return check(l,mid)?solve(l,mid):solve(mid+1,r);
}
int main() {
    int i,ans; read(T);
    while (T--) {
        for (read(n),i=1;i<=n;i++) read(b[i].l),read(b[i].r),read(b[i].d);
        ans=solve(0,infi);
        if (ans>=0) printf("%d %d\n",ans,sum);
        else puts("Poor QIN Teng:(");
    }
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=20010;
struct node{int x,y,z;}a[N],b[N];
int n,m,k,fa[N];
bool cmp(const node &a,const node &b) {return a.z<b.z;}
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
void read(int &a) {
    char ch; while (!((ch=getchar())>='0'&&ch<='9'));
    a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
bool check(int cost) {
    int i,tot=0,block=n,fx,fy;
    for (i=1;i<=n;i++) fa[i]=i;
    for (i=1;i<m;i++) {
        if (a[i].z>cost) break;
        fx=find(a[i].x);
        fy=find(a[i].y);
        if (fx==fy) continue;
        fa[fx]=fy; block--; tot++;
    } if (tot<k) return 0;
    for (i=1;i<m;i++) {
        if (b[i].z>cost) break;
        fx=find(b[i].x);
        fy=find(b[i].y);
        if (fx==fy) continue;
        fa[fx]=fy; block--;
    } return block==1;
}
int main() {
    int i,l=1,r=30000,mid;
    read(n); read(k); read(m);
    for (i=1;i<m;i++) {
        read(a[i].x); read(a[i].y); read(a[i].z);
        b[i].x=a[i].x; b[i].y=a[i].y; read(b[i].z);
    }
    sort(a+1,a+m,cmp);
    sort(b+1,b+m,cmp);
    while (l<r) {
        mid=(l+r)>>1;
        if (check(mid)) r=mid;
        else l=mid+1;
    } printf("%d\n",l);
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=200;
int n,d[N],sum,p[N],num[N],tot;
bool b[N],ok;
ll ans;
void read(int &a) {
    char ch; while (!((ch=getchar())>='0'&&ch<='9'));
    a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
void calc(int n,int k) {
    int i,j,x;
    for (i=1;i<=n;i++)
        for (j=2,x=i;j<=i;j++) 
            while (x%j==0) x/=j,num[j]+=k;
}
int main() {
    int i,j,x;
    for (read(n),i=1;i<=n;i++) {
        read(d[i]); d[i]--; sum+=d[i];
    }
    if (sum!=n-2) return puts("0"),0;
    if (n==1) return puts("1"),0;
    calc(sum,1);
    for (i=1;i<=n;i++) {
        if (d[i]<0) return puts("0"),0;
        if (!d[i]) continue;
        calc(d[i],-1);
    }
    for (ans=i=1;i<=n;i++) if (num[i]) 
        while (num[i]>0) ans*=(ll)i,num[i]--;
    cout<<ans<<endl;
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=10000100;
int n,m,len,head[200100];
int son[N][2],fa[N],lastans;
void read(int &a) {
    char ch; while (!((ch=getchar())>='0'&&ch<='9'));
    a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
int build(int l,int r) {
    int t=++len,mid=(l+r)>>1;
    if (l==r) {
        fa[t]=l;
        return t;
    }
    son[t][0]=build(l,mid);
    son[t][1]=build(mid+1,r);
    return t;
}
int ask(int i,int l,int r,int x) {
    if (l==r) return fa[i];
    int mid=(l+r)>>1;
    return x<=mid?ask(son[i][0],l,mid,x):ask(son[i][1],mid+1,r,x);
}
int change(int i,int l,int r,int x,int y) {
    int t=++len,mid=(l+r)>>1;
    if (l==r) {
        fa[t]=y;
        return t;
    }
    if (x<=mid) son[t][0]=change(son[i][0],l,mid,x,y),son[t][1]=son[i][1];
    else son[t][1]=change(son[i][1],mid+1,r,x,y),son[t][0]=son[i][0];
    return t;
}
int find(int x,int k) {
    int t=ask(head[k],1,n,x);
    if (t==x) return t;
    else return head[k]=change(head[k],1,n,x,t=find(t,k)),t;
}
int main() {
    int i,k,x,y,fx,fy;
    read(n); read(m);
    head[0]=build(1,n);
    for (i=1;i<=m;i++) {
        head[i]=head[i-1];
        read(k); read(x); x^=lastans;
        if (k==2) head[i]=head[x];
        else read(y),y^=lastans;
        if (k==1) {
            fx=find(x,i); fy=find(y,i);
            if (fx!=fy) head[i]=change(head[i],1,n,fx,fy);
        } else if (k==3) {
            fx=find(x,i); fy=find(y,i);
            printf("%d\n",lastans=(fx==fy));
        }
    }
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
ll k,n,i,l,r;
ll ans;
int main() {
    cin>>k>>n;
    if (k>n) ans=(k-n)*n;
    for (i=1;i*i<=n&&i<=k;i++) ans+=n%i;
    for (i=1;i*i<=n;i++) {
        l=n/(i+1)+1; r=n/i;
        if (l*l<=n) break;
        if (l>k) continue;
        r=min(r,k);
        ans+=(ll)(n%l+n%r)*(r-l+1)/2;
    } cout<<ans<<endl;
    return 0;
}
def A(n,m):
    if (m>n):return 0
    ans=1
    for i in range(m):
        ans=ans*(n-i)
    return ans
def multi(x):
    ans=1
    for i in range(x):
        ans=ans*(i+1)
    return ans
n,m=map(int,raw_input().split())
ans=multi(n)*A(n+1,2)*A(n+3,m)
ans=ans+multi(n)*m*(n+1)*A(n+2,m-1)*2
print ans
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=500010;
int n,m,t,num[N][2],len[N],lazy[N];
int lenl[N][2],lenr[N][2],ma[N][2];
int sumr,ans;
void read(int &a) {
    char ch; while (!((ch=getchar())>='0'&&ch<='9'));
    a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
void Max(int &x,int y) {if (x<y) x=y;}
void updata(int i,int k) {
    num[i][k]=num[i<<1][k]+num[i<<1|1][k];
    lenl[i][k]=lenl[i<<1][k];
    if (lenl[i<<1][k]==len[i<<1]) Max(lenl[i][k],len[i<<1]+lenl[i<<1|1][k]);
    lenr[i][k]=lenr[i<<1|1][k];
    if (lenr[i<<1|1][k]==len[i<<1|1]) Max(lenr[i][k],len[i<<1|1]+lenr[i<<1][k]);
    ma[i][k]=lenr[i<<1][k]+lenl[i<<1|1][k];
    Max(ma[i][k],ma[i<<1][k]);
    Max(ma[i][k],ma[i<<1|1][k]);
}
void build(int i,int l,int r) {
    len[i]=r-l+1; lazy[i]=-1;
    if (l==r) {
        read(t); num[i][t]=1;
        lenl[i][t]=lenr[i][t]=ma[i][t]=1;
        return;
    } int mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    updata(i,0); updata(i,1);
}
void add(int i,int k) {
    if (lazy[i]==-1) lazy[i]=k;
    else if (k<2) lazy[i]=k;
    else if (lazy[i]>-1&&lazy[i]<2) lazy[i]^=1;
    else if (lazy[i]==2) lazy[i]=-1;
}
void clean(int i) {
    if (!i) return;
    if (lazy[i]>-1) {
        if (lazy[i]<2) {
            num[i][lazy[i]]=len[i];
            lenl[i][lazy[i]]=len[i];
            lenr[i][lazy[i]]=len[i];
            ma[i][lazy[i]]=len[i];
            num[i][lazy[i]^1]=0;
            lenl[i][lazy[i]^1]=0;
            lenr[i][lazy[i]^1]=0;
            ma[i][lazy[i]^1]=0;
        } else {
            swap(num[i][0],num[i][1]);
            swap(lenl[i][0],lenl[i][1]);
            swap(lenr[i][0],lenr[i][1]);
            swap(ma[i][0],ma[i][1]);
        }
        add(i<<1,lazy[i]); 
        add(i<<1|1,lazy[i]);
        lazy[i]=-1;
    }
}
void modify(int i,int l,int r,int x,int y,int z) {
    clean(i);
    if (x<=l&&y>=r) {
        lazy[i]=z;
        clean(i);
        return;
    } int mid=(l+r)>>1;
    if (x<=mid) modify(i<<1,l,mid,x,y,z);
    if (y>mid) modify(i<<1|1,mid+1,r,x,y,z);
    clean(i<<1); clean(i<<1|1);
    updata(i,0); 
    updata(i,1);
}
int ask(int i,int l,int r,int x,int y) {
    clean(i);
    if (x<=l&&y>=r) return num[i][1];
    int mid=(l+r)>>1,ans=0;
    if (x<=mid) ans+=ask(i<<1,l,mid,x,y);
    if (y>mid) ans+=ask(i<<1|1,mid+1,r,x,y);
    return ans;
}
void get(int i,int l,int r,int x,int y) {
    clean(i);
    if (x<=l&&y>=r) {
        Max(ans,ma[i][1]);
        Max(ans,sumr+lenl[i][1]);
        if (lenr[i][1]==len[i]) sumr+=len[i];
        else sumr=lenr[i][1];
        return;
    } int mid=(l+r)>>1;
    if (x<=mid) get(i<<1,l,mid,x,y);
    if (y>mid) get(i<<1|1,mid+1,r,x,y);
}
int query(int l,int r,int x,int y) {
    ans=sumr=0; get(1,l,r,x,y);
    return ans;
}
void print(int i,int l,int r) {
    clean(i);
    if (l==r) {
        printf("%d ",num[i][1]);
        return;
    } int mid=(l+r)>>1;
    print(i<<1,l,mid);
    print(i<<1|1,mid+1,r);
}
int main() {
    int i,k,x,y;
    read(n); read(m);
    build(1,0,n-1);
    for (i=1;i<=m;i++) {
        read(k); read(x); read(y);
        if (k==0) modify(1,0,n-1,x,y,0);
        else if (k==1) modify(1,0,n-1,x,y,1);
        else if (k==2) modify(1,0,n-1,x,y,2);
        else if (k==3) printf("%d\n",ask(1,0,n-1,x,y));
        else if (k==4) printf("%d\n",query(0,n-1,x,y));
    }
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=100010;
int T,n;
int g[210],to[N],nxt[N],tot;
int h[210],pt[N],lik[N],cnt;
int belong[210];
bool v[210],ans;
void read(int &a) {
    char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
    if (ch=='-') f=1; else a=ch-'0'; 
    while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
    if (f) a=-a;
}
void addedge(int x,int y) {
    to[++tot]=y; nxt[tot]=g[x]; g[x]=tot;
    pt[++cnt]=x; lik[cnt]=h[y]; h[y]=cnt;
}
bool find1(int x){
    for (int k=g[x];k;k=nxt[k]){
        if (!v[to[k]]) {
            v[to[k]]=1;
            if (!belong[to[k]]||find1(belong[to[k]])) {
                belong[to[k]]=x;
                return 1;
            }
        }
    }
    return 0;
}
bool find2(int x){
    for (int k=h[x];k;k=lik[k]){
        if (!v[pt[k]]) {
            v[pt[k]]=1;
            if (!belong[pt[k]]||find2(belong[pt[k]])) {
                belong[pt[k]]=x;
                return 1;
            }
        }
    }
    return 0;
} 
int main() {
    int i,j,x;
    read(T);
    while (T--) {
        read(n); tot=cnt=0;
        for (i=1;i<=n;i++) g[i]=h[i]=0;
        for (i=1;i<=n;i++) {
            for (j=1;j<=n;j++) {
                read(x); 
                if (x==1) addedge(i,j);
            }
        } ans=true;
        memset(belong,0,sizeof(belong));
        for (i=1;i<=n;i++) {
            memset(v,0,sizeof(v));
            if (!find1(i)) {
                ans=false;
                break;
            }
        }
        if (ans) {
            memset(belong,0,sizeof(belong));
            for (i=1;i<=n;i++) {
                memset(v,0,sizeof(v));
                if (!find2(i)) {
                    ans=false;
                    break;
                }
            }
        }
        if (ans) puts("Yes");
        else puts("No");
    }
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=200010;
int n,m,root;
int fa[N],v[N],mi[N<<1],lazy[N<<1];
int pos[N],dfn[N],ed[N],df;
int d[N],top[N],son[N],num[N];
int g[N],to[N],nxt[N],tot;
void read(int &a) {
    char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
    if (ch=='-') f=1; else a=ch-'0'; 
    while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
    if (f) a=-a;
}
void Min(int &x,int y) {if (x>y) x=y;}
void addedge(int x,int y) {
    to[++tot]=y; nxt[tot]=g[x]; g[x]=tot;
    to[++tot]=x; nxt[tot]=g[y]; g[y]=tot;
}
void dfs1(int x,int fat) {
    fa[x]=fat; 
    for (int k=g[x];k;k=nxt[k]) {
        if (to[k]==fat) continue;
        dfs1(to[k],x);
        if (num[to[k]]>num[son[x]]) son[x]=to[k];
        num[x]+=num[to[k]];
    } num[x]++;
}
void dfs2(int x,int t,int dep) {
    dfn[x]=++df; pos[df]=x; 
    top[x]=t; d[x]=dep;
    if (son[x]) dfs2(son[x],t,dep+1);
    for (int k=g[x];k;k=nxt[k]) {
        if (to[k]==fa[x]||to[k]==son[x]) continue;
        dfs2(to[k],to[k],dep+1);
    } ed[x]=df;
}
void build(int i,int l,int r) {
    if (l==r) {
        mi[i]=v[pos[l]];
        return;
    } int mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    mi[i]=min(mi[i<<1],mi[i<<1|1]);
}
void clean(int i,int l,int r) {
    if (!i) return;
    if (lazy[i]) {
        mi[i]=lazy[i];
        if (l!=r) lazy[i<<1]=lazy[i<<1|1]=lazy[i];
        lazy[i]=0;
    }
}
void change(int i,int l,int r,int x,int y,int z) {
    clean(i,l,r);
    if (x<=l&&y>=r) {
        lazy[i]=z;
        clean(i,l,r);
        return;
    } int mid=(l+r)>>1;
    if (x<=mid) change(i<<1,l,mid,x,y,z);
    if (y>mid) change(i<<1|1,mid+1,r,x,y,z);
    clean(i<<1,l,mid); clean(i<<1|1,mid+1,r);
    mi[i]=min(mi[i<<1],mi[i<<1|1]);
    return;
}
void modify(int x,int y,int z) {
    while (top[x]!=top[y]) {
        if (d[top[x]]<d[top[y]]) change(1,1,n,dfn[top[y]],dfn[y],z),y=fa[top[y]];
        else change(1,1,n,dfn[top[x]],dfn[x],z),x=fa[top[x]];
    }
    if (d[x]<d[y]) change(1,1,n,dfn[x],dfn[y],z);
    else change(1,1,n,dfn[y],dfn[x],z);
}
int ask(int i,int l,int r,int x,int y) {
    if (x>y) return infi;
    clean(i,l,r);
    if (x<=l&&y>=r) return mi[i];
    int mid=(l+r)>>1,ans=infi;
    if (x<=mid) Min(ans,ask(i<<1,l,mid,x,y));
    if (y>mid) Min(ans,ask(i<<1|1,mid+1,r,x,y));
    return ans;
}
int get(int x,int y) {
    int last=y;
    for (;top[y]!=top[x];last=top[y],y=fa[top[y]]);
    return y==x?last:son[x];
}
int query(int x) {
    if (x==root) return ask(1,1,n,1,n);
    else if (dfn[x]<=dfn[root]&&ed[x]>=dfn[root]) {
        int t=get(x,root),ans=infi;
        Min(ans,ask(1,1,n,1,dfn[t]-1));
        Min(ans,ask(1,1,n,ed[t]+1,n));
        return ans;
    } else return ask(1,1,n,dfn[x],ed[x]);
}
int main() {
    int i,k,x,y,z;
    read(n); read(m);
    for (i=1;i<n;i++) {
        read(x); read(y);
        addedge(x,y);
    }
    dfs1(1,0); dfs2(1,1,1);
    for (i=1;i<=n;i++) read(v[i]);
    read(root);
    build(1,1,n);
    for (i=1;i<=m;i++) {
        read(k); read(x);
        if (k==2) read(y),read(z);
        if (k==1) root=x;
        else if (k==2) modify(x,y,z);
        else if (k==3) printf("%d\n",query(x));
    }
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=100010;
const int M=110;
const int u[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m,ans,a[M][M],id[M][M],cnt;
int g[N],to[N],nxt[N],f[N],tot=1;
int gap[N],h[N],d[N],s,t;
void read(int &a) {
    char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
    if (ch=='-') f=1; else a=ch-'0'; 
    while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
    if (f) a=-a;
}
void addedge(int x,int y,int z) {
    to[++tot]=y; nxt[tot]=g[x]; g[x]=tot; f[tot]=z;
    to[++tot]=x; nxt[tot]=g[y]; g[y]=tot; f[tot]=0;
}
int iSap(int x,int flow){
    if (x==t) return flow;
    int k,nowflow=0,rec;
    for (k=h[x];k;k=nxt[k]) if (d[x]==d[to[k]]+1&&f[k]) {
        rec=iSap(to[k],min(flow-nowflow,f[k]));
        f[k]-=rec; f[k^1]+=rec; h[x]=k;
        if ((nowflow+=rec)==flow) return flow;
    }
    h[x]=g[x];
    if (!(--gap[d[x]])) d[s]=n;
    gap[++d[x]]++;
    return nowflow;
}
int main() {
    int i,j,k,x,y;
    read(n); read(m); 
    for (i=1;i<=n;i++) for (j=1;j<=m;j++) read(a[i][j]),id[i][j]=++cnt;
    s=++cnt; t=++cnt;
    for (i=1;i<=n;i++) for (j=1;j<=m;j++) {
        if (a[i][j]==1) {
            addedge(s,id[i][j],infi);
            for (k=0;k<4;k++) {
                x=i+u[k][0]; y=j+u[k][1];
                if (x<1||x>n||y<1||y>m) continue;
                if (a[x][y]==1) continue;
                addedge(id[i][j],id[x][y],1);
            }
        } else if (a[i][j]==2) addedge(id[i][j],t,infi);
        else if (a[i][j]==0) {
            for (k=0;k<4;k++) {
                x=i+u[k][0]; y=j+u[k][1];
                if (x<1||x>n||y<1||y>m) continue;
                if (a[x][y]==1) continue;
                addedge(id[i][j],id[x][y],1);
            }
        }
    }
    for (i=1;i<=t;i++) h[i]=g[i];
    gap[0]=n=t;
    while (d[s]<n) ans+=iSap(s,infi);
    printf("%d\n",ans);
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=100010;
int n,m,ma[N<<3],tot;
int a[N],b[N],c[N],d[N];
void Max(int &x,int y) {if (x<y) x=y;}
void read(int &a) {
    char ch; bool f=0; while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
    if (ch=='-') f=1,a=0; else a=ch-'0'; 
    while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
    if (f) a=-a;
}
void build(int i,int l,int r) {
    if (l==r) {
        ma[i]=b[l];
        return;
    } int mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    ma[i]=max(ma[i<<1],ma[i<<1|1]);
}
int ask(int i,int l,int r,int x,int y) {
    if (x>y) return 0;
    if (x<=l&&y>=r) return ma[i];
    int mid=(l+r)>>1,ans=0;
    if (x<=mid) Max(ans,ask(i<<1,l,mid,x,y));
    if (y>mid) Max(ans,ask(i<<1|1,mid+1,r,x,y));
    return ans;
}
int check(int l,int r,int x) {
    int mid=0;
    while (l<r) {
        mid=(l+r)>>1;
        if (x<=a[mid]) r=mid;
        else l=mid+1;
    } return r;
}
int main() {
    int i,x,y,tx,ty,tmp;
    for (read(n),i=1;i<=n;i++) read(a[i]),read(b[i]);
    build(1,1,n); a[n+1]=infi; a[0]=-infi;
    for (read(m),i=1;i<=m;i++) {
        read(x); read(y);
        tx=check(0,n+1,x);
        ty=check(0,n+1,y);
        if (a[tx]!=x&&a[ty]!=y) puts("maybe");
        else if (x==y) puts("true");
        else if (a[tx]!=x&&a[ty]==y) {
            tmp=ask(1,1,n,tx,ty-1);
            if (tmp>=b[ty]) puts("false");
            else puts("maybe");
        } else if (a[ty]!=y&&a[tx]==x) {
            tmp=ask(1,1,n,tx+1,ty-1);
            if (tmp>=b[tx]) puts("false");
            else puts("maybe");
        } else if (b[tx]<b[ty]) puts("false");
        else {
            tmp=ask(1,1,n,tx+1,ty-1);
            if (tmp>=b[ty]) puts("false");
            else if (y-x!=ty-tx) puts("maybe");
            else puts("true");
        }
    }
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=100010;
char s[10];
int n,m,a[N];
ll h[N][2];
void add(int pos,ll x,int k) {while (pos<=n) h[pos][k]+=x,pos+=pos&-pos;}
ll sum(int pos,int k){ll t=0; while (pos>0) t+=h[pos][k],pos-=pos&-pos;return t;}
void read(int &a) {
    char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
    if (ch=='-') f=1; else a=ch-'0'; 
    while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
    if (f) a=-a;
}
int main() {
    int i,x,y;
    read(n); read(m);
    for (i=1;i<=n;i++) read(a[i]),add(i,a[i],0),add(i,(ll)a[i]*(n-i+1),1);
    for (i=1;i<=m;i++) {
        scanf("%s",&s); read(x);
        if (s[0]=='Q') printf("%lld\n",sum(x,1)-(ll)sum(x,0)*(n-x));
        else read(y),add(x,y-a[x],0),add(x,(ll)(y-a[x])*(n-x+1),1),a[x]=y;
    }
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=100010;
int n,m; char s[10];
int ma[N<<2],evma[N<<2],la[N<<2][2],evla[N<<2][2];
bool f[N<<2];
void read(int &a) {
    char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||(ch=='-')));
    if (ch=='-') f=1,a=0; else a=ch-'0';
    while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
    if (f) a=-a;
}
void build(int i,int l,int r) {
    if (l==r) {
        read(ma[i]);
        evma[i]=ma[i];
        return;
    } int mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    ma[i]=max(ma[i<<1],ma[i<<1|1]);
    evma[i]=ma[i];
}
void add(int i,int x,int y) {
    if (!f[i]) {
        if (la[i][0]+y>evla[i][0]) evla[i][0]=la[i][0]+y;
        la[i][0]+=x;
    } else {
        if (la[i][1]+y>evla[i][1]) evla[i][1]=la[i][1]+y;
        la[i][1]+=x;
    }
}
void clean(int i,int l,int r) {
    if (!i) return;
    if (la[i][0]||evla[i][0]||f[i]) {
        if (la[i][0]||evla[i][0]) {
            if (ma[i]+evla[i][0]>evma[i]) evma[i]=ma[i]+evla[i][0];
            ma[i]+=la[i][0];
            if (l!=r) {
                add(i<<1,la[i][0],evla[i][0]);
                add(i<<1|1,la[i][0],evla[i][0]);
            }
            la[i][0]=evla[i][0]=0;
        }
        if (f[i]) {
            if (evla[i][1]>evma[i]) evma[i]=evla[i][1];
            ma[i]=la[i][1];
            if (l!=r) {
                if (evla[i][1]>evla[i<<1][1]) evla[i<<1][1]=evla[i][1];
                if (evla[i][1]>evla[i<<1|1][1]) evla[i<<1|1][1]=evla[i][1];
                la[i<<1][1]=la[i<<1|1][1]=la[i][1];
                f[i<<1]=f[i<<1|1]=1;
            } f[i]=0;
            la[i][1]=0; evla[i][1]=-infi;
        }
    }
}
void add(int i,int l,int r,int x,int y,int z) {
    clean(i,l,r);
    if (x<=l&&y>=r) {
        la[i][0]=z;
        if (la[i][0]>evla[i][0]) evla[i][0]=la[i][0];
        clean(i,l,r);
        return;
    } int mid=(l+r)>>1;
    if (x<=mid) add(i<<1,l,mid,x,y,z);
    if (y>mid) add(i<<1|1,mid+1,r,x,y,z);
    clean(i<<1,l,mid); clean(i<<1|1,mid+1,r);
    ma[i]=max(ma[i<<1],ma[i<<1|1]);
    if (ma[i]>evma[i]) evma[i]=ma[i];
}
void change(int i,int l,int r,int x,int y,int z) {
    clean(i,l,r);
    if (x<=l&&y>=r) {
        la[i][1]=z;
        evla[i][1]=z;
        f[i]=1;
        clean(i,l,r);
        return;
    } int mid=(l+r)>>1;
    if (x<=mid) change(i<<1,l,mid,x,y,z);
    if (y>mid) change(i<<1|1,mid+1,r,x,y,z);
    clean(i<<1,l,mid); clean(i<<1|1,mid+1,r);
    ma[i]=max(ma[i<<1],ma[i<<1|1]);
    if (ma[i]>evma[i]) evma[i]=ma[i];
}
int query(int i,int l,int r,int x,int y) {
    clean(i,l,r);
    if (x<=l&&y>=r) return ma[i];
    int mid=(l+r)>>1,ans=-infi;
    if (x<=mid) ans=max(ans,query(i<<1,l,mid,x,y));
    if (y>mid) ans=max(ans,query(i<<1|1,mid+1,r,x,y));
    return ans;
}
int ask(int i,int l,int r,int x,int y) {
    clean(i,l,r);
    if (x<=l&&y>=r) return evma[i];
    int mid=(l+r)>>1,ans=-infi;
    if (x<=mid) ans=max(ans,ask(i<<1,l,mid,x,y));
    if (y>mid) ans=max(ans,ask(i<<1|1,mid+1,r,x,y));
    return ans;
}
int main() {
    int i,x,y,z;
    read(n); build(1,1,n);
    for (read(m),i=1;i<=m;i++) {
        scanf("%s",&s); read(x); read(y);
        if (s[0]=='P'||s[0]=='C') read(z);
        if (s[0]=='Q') printf("%d\n",query(1,1,n,x,y));
        else if (s[0]=='A') printf("%d\n",ask(1,1,n,x,y));
        else if (s[0]=='P') add(1,1,n,x,y,z);
        else if (s[0]=='C') change(1,1,n,x,y,z);
    }
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=1000100;
int n,a,b,c;
ll g[N],s[N];
int team[N],head,tail;
void read(ll &a) {
    char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
    if (ch=='-') f=1; else a=ch-'0'; 
    while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
    if (f) a=-a;
}
ll calc(int x,int y) {return a*(s[x]-s[y])*(s[x]-s[y])+c+g[y];}
ll calc2(int x,int y) {return g[x]-g[y]+a*s[x]*s[x]-a*s[y]*s[y];}
bool check(int i,int j,int k) {return calc2(i,j)*2*a*(s[j]-s[k])<calc2(j,k)*2*a*(s[i]-s[j]);}
int main() {
    int i;
    scanf("%d%d%d%d",&n,&a,&b,&c);
    for (i=1;i<=n;i++) read(s[i]),s[i]+=s[i-1];
    team[head=tail=1]=0;
    for (i=1;i<=n;i++) {
        while (head<tail&&calc(i,team[head])<calc(i,team[head+1])) head++;
        g[i]=calc(i,team[head]);
        while (head<tail&&check(i,team[tail],team[tail-1])) tail--;
        team[++tail]=i;
    } cout<<g[n]+(ll)b*s[n]<<endl;
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
D x,y,ma,mi,ans=100000000.0;
int n;
void Max(D &x,D y) {if (x<y) x=y;}
void Min(D &x,D y) {if (x>y) x=y;}
D solve(D x,D y,int n) {
    if (n==1) return max(x/y,y/x);
    int i; D ans=100000000.0,tx,ty;
    for (i=1;i<n;i++) {
        tx=x*(i+0.0)/(n+0.0);
        Min(ans,max(solve(tx,y,i),solve(x-tx,y,n-i)));
    }
    for (i=1;i<n;i++) {
        ty=y*(i+0.0)/(n+0.0);
        Min(ans,max(solve(x,ty,i),solve(x,y-ty,n-i)));
    } return ans;
}
int main() {
    scanf("%lf%lf%d",&x,&y,&n);
    printf("%.6lf\n",solve(x,y,n));
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=150010;
priority_queue<int>q;
struct node{int x,y;}a[N];
int n,t,ans;
void read(int &a) {
    char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
    if (ch=='-') f=1,a=0; else a=ch-'0'; 
    while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
    if (f) a=-a;
}
bool cmp(const node &a,const node &b) {return a.y<b.y||a.y==b.y&&a.x<b.x;}
int main() {
    int i;
    for (read(n),i=1;i<=n;i++) 
        read(a[i].x),read(a[i].y);
    sort(a+1,a+1+n,cmp);
    for (i=1;i<=n;i++) {
        if (a[i].x+t<=a[i].y) t+=a[i].x,q.push(a[i].x),ans++;
        else if (a[i].x<=q.top()) {
            if (t-q.top()+a[i].x<=a[i].y) 
                t=t-q.top()+a[i].x,q.pop(),q.push(a[i].x);
        }
    } cout<<ans<<endl;
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=1000100;
int n,i,j,p[N],c[N];
int team[N],head,tail;
ll s[N],g[N],f[N],d[N];
ll calc(int j,int i) {return f[j]+g[i]-g[j]-s[j]*(d[i]-d[j]);}
ll calc2(int i,int j) {return s[i]*d[i]-g[i]+f[i]-s[j]*d[j]+g[j]-f[j];}
bool check(int i,int j,int k) {return calc2(i,j)*(s[j]-s[k])<calc2(j,k)*(s[i]-s[j]);}
int main() {
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%lld%d%d",&d[i],&p[i],&c[i]);
    for (i=1;i<=n;i++) s[i]=s[i-1]+p[i],g[i]=g[i-1]+s[i-1]*(d[i]-d[i-1]);
    team[head=tail=1]=0;
    for (i=1;i<=n;i++) {
        while (head<tail&&calc(team[head],i)>calc(team[head+1],i)) head++;
        f[i]=calc(team[head],i)+c[i];
        while (head<tail&&check(i,team[tail],team[tail-1])) tail--;
        team[++tail]=i;
    } cout<<f[n]<<endl;
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=10010;
struct node{int t,x,y;}a[N];
int i,j,n,m,f[N],ans;
void read(int &a) {
    char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
    if (ch=='-') f=1,a=0; else a=ch-'0'; 
    while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
    if (f) a=-a;
}
int Abs(int x) {return x>0?x:-x;}
void Max(int &x,int y) {if (x<y) x=y;}
int main() {
    read(n); read(m);
    for (i=1;i<=m;i++) read(a[i].t),read(a[i].x),read(a[i].y);
    for (i=1;i<=m;i++) {
        f[i]=1;
        for (j=1;j<i;j++) {
            if (a[i].t-a[j].t>=Abs(a[i].x-a[j].x)+Abs(a[i].y-a[j].y))
                Max(f[i],f[j]+1);
        } Max(ans,f[i]);
    } cout<<ans<<endl;
    return 0;
}
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,q,g[305][305];
int h[105][305][305];
void add(int k,int x,int pos,int z) {while (pos<=m) h[k][x][pos]+=z,pos+=(pos&(-pos));}
void insert(int k,int x,int y,int z) {while (x<=n) add(k,x,y,z),x+=(x&(-x));}
int ask(int k,int x,int pos) {int t=0; while (pos>0) t+=h[k][x][pos],pos-=(pos&(-pos));return t;}
int get(int k,int x,int y) {int t=0; while (x>0) t+=ask(k,x,y),x-=(x&(-x));return t;}
int main() {
    int i,j,ans; int c,k,x1,x2,y1,y2;
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++) for (j=1;j<=m;j++) {
        scanf("%d",&g[i][j]);
        insert(g[i][j],i,j,1);
    } scanf("%d",&q);
    for (i=1;i<=q;i++) {
        scanf("%d",&k);
        if (k==1) {
            scanf("%d%d%d",&x1,&y1,&c);
            insert(g[x1][y1],x1,y1,-1);
            g[x1][y1]=c;
            insert(g[x1][y1],x1,y1,1);
        } else {
            scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);
            ans=get(c,x2,y2)+get(c,x1-1,y1-1);
            ans=ans-get(c,x1-1,y2)-get(c,x2,y1-1);
            printf("%d\n",ans);
        }
    }
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=3010;
const int M=200010;
vector<int>v[N];
int n,m,d[N],w[N],ed[N];
int g[N],c[M],to[M],nxt[M],tot;
bool b[N];
void read(int &a) {
    char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
    if (ch=='-') f=1,a=0; else a=ch-'0'; 
    while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
    if (f) a=-a;
}
void addedge(int x,int y,int z) {
    to[++tot]=y; nxt[tot]=g[x]; g[x]=tot; c[tot]=z;
}
void Max(int &x,int y) {if (x<y) x=y;}
void dijkstra() {
    int i,j,sz,x,k,ma;
    for (i=1;i<=n;i++) d[i]=infi; d[1]=0;
    for (i=1;i<=n;i++) {
        ma=infi;
        for (j=1;j<=n;j++) if (!b[j]&&!w[j]&&d[j]<ma) ma=d[j],x=j;
        sz=v[x].size(); b[x]=1;
        for (j=0;j<sz;j++) {
            w[v[x][j]]--;
            if (!w[v[x][j]]) Max(d[v[x][j]],d[x]);
        }
        for (k=g[x];k;k=nxt[k]) if (d[x]+c[k]<d[to[k]])
            d[to[k]]=d[x]+c[k];
    }
}
int main() {
    int i,j,x,y,z;
    read(n); read(m);
    for (i=1;i<=m;i++) {
        read(x); read(y); read(z);
        addedge(x,y,z);
    }
    for (i=1;i<=n;i++) {
        read(w[i]);
        for (j=1;j<=w[i];j++) {
            read(x);
            v[x].push_back(i);
        }
    } dijkstra();
    cout<<d[n]<<endl;
    return 0;
}
#include <cstdio>
using namespace std;
typedef long long ll;
int n;
ll ans;
int main() {
    scanf("%d",&n);
    for (int i=1;i<=n;i++) ans+=n/i;
    printf("%lld\n",ans);
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=10001000;
int n,prime[N],phi[N],tot;
ll f[N],ans;
bool b[N];
void calc(int x){
    b[1]=1;
    int num,i;
    for (i=2;i<=n;i++) phi[i]=i;
    for (i=2;i<=x;i++){
        if (b[i]) continue;
        prime[++tot]=i;num=i;
        while (num<=x) b[num]=1,(phi[num]/=i)*=(i-1),num+=i;
    }
}
int main() {
    int i;
    scanf("%d",&n);
    calc(n);
    for (i=2;i<=n;i++) f[i]=(f[i-1]+phi[i]);
    for (i=1;i<=n;i++) f[i]=f[i]<<1|1;
    for (i=1;prime[i]<=n&&i<=tot;i++) ans+=f[n/prime[i]];
    cout<<ans<<endl;
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=1000100;
int n,a[N];
ll f[N],sum,need,tmp,ans;
void read(int &a) {
    char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
    if (ch=='-') f=1,a=0; else a=ch-'0'; 
    while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
    if (f) a=-a;
}
int Abs(int x) {return x>0?x:-x;}
int main() {
    int i;
    for (read(n),i=1;i<=n;i++) read(a[i]),sum+=a[i];
    need=sum/n;
    for (i=2;i<=n;i++) f[i]=need+f[i-1]-a[i];
    sort(f+1,f+1+n);
    tmp=f[n/2];
    for (i=1;i<=n;i++) ans+=Abs(f[i]-tmp);
    cout<<ans<<endl;
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=1010;
struct node{int x,y;}a[N];
int n,k,fa[N];
D d[N][N],l,r,mid;
void read(int &a) {
    char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
    if (ch=='-') f=1,a=0; else a=ch-'0'; 
    while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
    if (f) a=-a;
}
int sqr(int x) {return x*x;}
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
bool check(D x) {
    int i,j,fx,fy,num=n;
    for (i=1;i<=n;i++) fa[i]=i;
    for (i=1;i<n;i++) for (j=i+1;j<=n;j++) 
        if (d[i][j]<=x) {
            fx=find(i); fy=find(j);
            if (fx==fy) continue;
            fa[fx]=fy;
            num--;
        }
    return num<k;
}
int main() {
    int i,j;
    read(n); read(k);
    for (i=1;i<=n;i++) read(a[i].x),read(a[i].y);
    for (i=1;i<n;i++) for (j=i+1;j<=n;j++) 
        d[i][j]=d[j][i]=sqrt(sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y));
    l=0.0; r=100000.0;
    while (r-l>eps) {
        mid=(l+r)/2.0;
        if (check(mid)) r=mid;
        else l=mid;
    } printf("%.2lf",l);
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=50010;
int n,phi[N],p[N],tot;
ll ans;
bool f[N];
void init() {
    int i,j,t; f[1]=f[0]=1;
    for (i=1;i<=n;i++) phi[i]=i;
    for (i=2;i<=n;i++) if (!f[i]) {
	    p[++tot]=i;
        for (j=i;j<=n;j+=i) {
		    f[j]=1;
		    phi[j]=phi[j]/i*(i-1);
		}
    }
}
int main() {
    scanf("%d",&n);
    init();
    for (int i=2;i<n;i++) ans+=phi[i];
    cout<<(ans<<1)+3<<endl;
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=51061;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=100010;
struct LCT *null;
struct LCT {
    LCT *fa,*son[2];
    int sz,id;
    int sum,v,lazy[2];
    bool rev;
    void newnode(int _id=0) {
        fa=son[0]=son[1]=null; id=_id;
        v=lazy[0]=sz=sum=1; lazy[1]=rev=0;
    }
    bool isroot() {return (fa==null)||(fa->son[0]!=this&&fa->son[1]!=this);}
    void updata() {
        LCT *x=this;
        x->sum=(son[0]->sum+son[1]->sum+v)%mod;
        x->sz=son[0]->sz+son[1]->sz+1;
    }
    void add(int x,int y) {
        LCT *t=this;
        if (t==null) return;
        t->v=((ll)t->v*x)%mod;
        t->v=(t->v+y)%mod;
        t->sum=((ll)t->sum*x)%mod;
        t->sum=(t->sum+(ll)y*t->sz)%mod;
        t->lazy[0]=((ll)t->lazy[0]*x)%mod;
        t->lazy[1]=((ll)t->lazy[1]*x)%mod;
        t->lazy[1]=(t->lazy[1]+y)%mod;
    }
    void reverse() {
        swap(son[0],son[1]);
        rev^=1;
    }
    void clean() {
        LCT *x=this;
        if (x==null) return;
        if (x->lazy[0]!=1||x->lazy[1]!=0) {
            x->son[0]->add(x->lazy[0],x->lazy[1]);
            x->son[1]->add(x->lazy[0],x->lazy[1]);
            x->lazy[0]=1; x->lazy[1]=0;
        }
        if (x->rev) {
            x->son[0]->reverse();
            x->son[1]->reverse();
            x->rev=0;
        }
    }
    void rotate() {
        LCT *x=this,*y=x->fa;
        int w=(y->son[0]==x);
        if (!y->isroot()) {
            LCT *z=y->fa;
            if (y==z->son[0]) z->son[0]=x;
            if (y==z->son[1]) z->son[1]=x;
        } x->fa=y->fa; y->fa=x;
        if (x->son[w]!=null) x->son[w]->fa=y;
        y->son[w^1]=x->son[w]; 
        x->son[w]=y; y->updata();
    }
    void clear() {
        if (this==null) return;
        if (!isroot()) fa->clear();
        this->clean();
    }
    void splay() {
        LCT *x=this,*y,*z; x->clear();
        while (!x->isroot()) {
            y=x->fa; z=y->fa;
            if (!y->isroot()) 
                if ((z->son[0]==y)^(y->son[1]==x)) y->rotate();
                else x->rotate();
            x->rotate();
        } x->updata();
    }
    void access() {
        LCT *x=this,*y=null;
        for (;x!=null;y=x,x=x->fa) {
            x->splay();
            x->son[1]=y;
            x->updata();
        }
    }
    void makeroot() {
        LCT *x=this;
        x->access();
        x->splay();
        x->reverse();
    }
};
LCT pool[N],*v[N],*cur;
int n,m;
char s[10];
void init() {
    cur=pool; null=cur++;
    null->newnode();
    null->sum=null->sz=null->v=0;
}
void read(int &a) {
    char ch; while (!((ch=getchar())>='0'&&ch<='9'));
    a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
void link(int x,int y) {
    v[y]->makeroot();
    v[y]->fa=v[x];
    v[y]->access();
}
void cut(int x,int y) {
    v[x]->makeroot();
    v[y]->access();
    v[y]->splay();
    v[y]->son[0]->fa=null;
    v[y]->son[0]=null;
    v[y]->updata();
}
void add(int x,int y,int z,int w) {
    v[x]->makeroot();
    v[y]->access();
    v[y]->splay();
    v[y]->add(z,w);
    v[y]->clean();
}
int query(int x,int y) {
    v[x]->makeroot();
    v[y]->access();
    v[y]->splay();
    return v[y]->sum;
}
int main() {
    int i,x,y,z,w,t;
    read(n); read(m); init();
    for (i=1;i<=n;i++) {
        v[i]=cur++;
        v[i]->newnode(i);
    }
    for (i=1;i<n;i++) {
        read(x); read(y);
        link(x,y);
    }
    for (i=1;i<=m;i++) {
        scanf("%s",&s); read(x); read(y);
        if (s[0]=='+') read(z),add(x,y,1,z);
        else if (s[0]=='*') read(z),add(x,y,z,0);
        else if (s[0]=='-') {
            cut(x,y);
            read(x);
            read(y);
            link(x,y);
        } else if (s[0]=='/') printf("%d\n",query(x,y));
    }
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=200010;
const int M=500010;
char s[10];
int n,m,w[N],num[N],fa[N];
int g[N],to[N],nxt[N],tot;
int top[N],pos[N],dfn[N],df;
int c[N],dep[N],lc[M],rc[M];
int lazy[M],cut[M];
int cur,ans;
void read(int &a) {
    char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
    if (ch=='-') f=1,a=0; else a=ch-'0'; 
    while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
    if (f) a=-a;
}
void addedge(int x,int y) {
    to[++tot]=y; nxt[tot]=g[x]; g[x]=tot;
    to[++tot]=x; nxt[tot]=g[y]; g[y]=tot;
}
void dfs(int x,int fat) {
    fa[x]=fat;
    for (int k=g[x];k;k=nxt[k]) if (to[k]!=fat) {
        dfs(to[k],x);
        if (num[to[k]]>num[w[x]]) w[x]=to[k];
        num[x]+=num[to[k]];
    } num[x]++;
}
void dfs2(int x,int depth,int tail) {
    dep[x]=depth; top[x]=tail;
    dfn[x]=++df; pos[df]=x;
    if (w[x]) dfs2(w[x],depth+1,tail);
    for (int k=g[x];k;k=nxt[k]) {
        if (to[k]==fa[x]||to[k]==w[x]) continue;
        dfs2(to[k],depth+1,to[k]);
    }
}
void build(int i,int l,int r) {
    lazy[i]=-1;
    if (l==r) {
        lc[i]=rc[i]=c[pos[l]];
        cut[i]=1;
        return;
    } int mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    cut[i]=cut[i<<1]+cut[i<<1|1];
    if (rc[i<<1]==lc[i<<1|1]) cut[i]--;
    lc[i]=lc[i<<1]; rc[i]=rc[i<<1|1];
}
void clean(int i,int l,int r) {
    if (!i) return;
    if (lazy[i]!=-1) {
        lc[i]=rc[i]=lazy[i];
        cut[i]=1;
        if (l!=r) lazy[i<<1]=lazy[i<<1|1]=lazy[i];
        lazy[i]=-1;
    }
}
void change(int i,int l,int r,int x,int y,int z) {
    clean(i,l,r);
    if (x<=l&&y>=r) {
        lazy[i]=z;
        clean(i,l,r);
        return;
    } int mid=(l+r)>>1;
    if (x<=mid) change(i<<1,l,mid,x,y,z);
    if (y>mid) change(i<<1|1,mid+1,r,x,y,z);
    clean(i<<1,l,mid); clean(i<<1|1,mid+1,r);
    cut[i]=cut[i<<1]+cut[i<<1|1];
    if (rc[i<<1]==lc[i<<1|1]) cut[i]--;
    lc[i]=lc[i<<1]; rc[i]=rc[i<<1|1];
}
void modify(int x,int y,int z) {
    while (top[x]!=top[y]) {
        if (dep[top[x]]>dep[top[y]]) change(1,1,n,dfn[top[x]],dfn[x],z),x=fa[top[x]];
        else change(1,1,n,dfn[top[y]],dfn[y],z),y=fa[top[y]];
    } dep[x]<dep[y]?change(1,1,n,dfn[x],dfn[y],z):change(1,1,n,dfn[y],dfn[x],z);
}
void ask(int i,int l,int r,int x,int y) {
    clean(i,l,r);
    if (x<=l&&y>=r) {
        ans+=cut[i];
        if (lc[i]==cur) ans--;
        cur=rc[i];
        return;
    } int mid=(l+r)>>1;
    if (x<=mid) ask(i<<1,l,mid,x,y);
    if (y>mid) ask(i<<1|1,mid+1,r,x,y);
}
int get(int x,int y) {
    ans=0; cur=-1;
    ask(1,1,n,x,y);
    return ans;
}
int get_c(int i,int l,int r,int x) {
    clean(i,l,r);
    if (l==r) return lc[i];
    int mid=(l+r)>>1;
    return x<=mid?get_c(i<<1,l,mid,x):get_c(i<<1|1,mid+1,r,x);
}
int query(int x,int y) {
    int ans=0,t1,t2;
    while (top[x]!=top[y]) {
        if (dep[top[x]]>dep[top[y]]) {
            ans+=get(dfn[top[x]],dfn[x]);
            t1=get_c(1,1,n,dfn[top[x]]);
            t2=get_c(1,1,n,dfn[fa[top[x]]]);
            if (t1==t2) ans--;
            x=fa[top[x]];
        } else {
            ans+=get(dfn[top[y]],dfn[y]);
            t1=get_c(1,1,n,dfn[top[y]]);
            t2=get_c(1,1,n,dfn[fa[top[y]]]);
            if (t1==t2) ans--;
            y=fa[top[y]];
        }
    }
    if (dep[x]<dep[y]) return ans+get(dfn[x],dfn[y]);
    else return ans+get(dfn[y],dfn[x]);
}
int main() {
    int i,x,y,z;
    read(n); read(m);
    for (i=1;i<=n;i++) read(c[i]);
    for (i=1;i<n;i++) {
        read(x); read(y);
        addedge(x,y);
    } dfs(1,0); dfs2(1,1,1);
    build(1,1,n);
    for (i=1;i<=m;i++) {
        scanf("%s",&s); read(x); read(y);
        if (s[0]=='C') {
            read(z);
            modify(x,y,z);
        } else if (s[0]=='Q') printf("%d\n",query(x,y));
    }
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=2000100;
int n,m,ans,belong[N];
int g[N],nxt[N],to[N],tot;
int v[N],c[N];
void addedge(int x,int y){
    to[++tot]=y; nxt[tot]=g[x]; g[x]=tot;
}
bool find(int x,int t){
    for (int k=g[x];k;k=nxt[k]){
        if (v[to[k]]!=t) {
            v[to[k]]=t;
            if (!belong[to[k]]||find(belong[to[k]],t)) {
                belong[to[k]]=x;
                return 1;
            }
        }
    }
    return 0;
}
void read(int &a) {
    char ch; bool f=0;while (!(((ch=getchar())>='0'&&ch<='9')||ch=='-'));
    if (ch=='-') f=1,a=0; else a=ch-'0'; 
    while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
    if (f) a=-a;
}
int main() {
    int i,x,y;
    for (read(n),i=1;i<=n;i++) {
        read(x); read(y);
        addedge(x,i);
        addedge(y,i);
        c[x]++; c[y]++;
    }
    for (i=1;;i++) {
        if (!c[i]) return printf("%d\n",i-1),0;
        if (!find(i,i)) return printf("%d\n",i-1),0;
    }
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
const int mod=12345678;
int n,x,y,K,ans;
int f[320][180][25][25];
int main() {
    int i,j,k,l;
    scanf("%d%d%d",&x,&y,&K); n=x+y;
    f[0][0][0][0]=1;
    for (i=0;i<n;i++) {
        for (j=0;j<=min(i,x);j++) for (k=0;k<=K;k++) for (l=0;l<=K;l++) {
            (f[i+1][j+1][k+1][max(l-1,0)]+=f[i][j][k][l])%=mod;
            (f[i+1][j][max(k-1,0)][l+1]+=f[i][j][k][l])%=mod;
        }
    }
    for (i=0;i<=K;i++) for (j=0;j<=K;j++) ans=(ans+f[n][x][i][j])%mod;
    printf("%d\n",ans);
    return 0;
}
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=400010;
const int infi=100000000;
int n,m,S,T,tot=1;
int g[510],nxt[N],to[N],f[N],c[N];
int mincost,tmpflow,ans;
int team[N],pre[510],d[510],head,tail;
bool in[510];
void addedge(int x,int y,int z,int w){
    to[++tot]=y; nxt[tot]=g[x]; g[x]=tot; f[tot]=z; c[tot]=w;
    to[++tot]=x; nxt[tot]=g[y]; g[y]=tot; f[tot]=0; c[tot]=-w;
}
bool spfa(){
    int i,k,x;
    for (i=S;i<=T;i++) d[i]=infi,in[i]=0;
    team[head=tail=0]=S;
    d[S]=0; in[S]=1;
    while (head<=tail){
        in[x=team[head++]]=0;
        for (k=g[x];k;k=nxt[k])
        if (f[k]&&d[x]+c[k]<d[to[k]]){
            d[to[k]]=d[x]+c[k];
            pre[to[k]]=k;
            if (!in[to[k]]) {
                in[to[k]]=1;
                team[++tail]=to[k];
            }
        }
    }
    return d[T]!=infi;
}
void augment(){
    int i; tmpflow=infi; ans++;
    for (i=pre[T];i;i=pre[to[i^1]]) tmpflow=min(tmpflow,f[i]);
    for (i=pre[T];i;i=pre[to[i^1]]) f[i]-=tmpflow,f[i^1]+=tmpflow,mincost+=c[i]*tmpflow;
}
int main(){
    int i,j,x,y,z;
    scanf("%d%d",&n,&m); S=1; T=n+n;
    for (i=1;i<=m;i++) {
        scanf("%d%d%d",&x,&y,&z);
        addedge(x+n,y,1,z);
    }
    for (i=2;i<n;i++) addedge(i,i+n,1,0);
    addedge(1,n+S,200,0); addedge(n,T,200,0);
    while (spfa()) augment();
    printf("%d %d\n",ans,mincost);
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=250010;
char s[10];
int n,m,fa[N];
int num[N],w[N],top[N],dfn[N],df;
int g[N],to[N<<1],nxt[N<<1],tot;
int f[N<<2];
void read(int &a) {
    char ch; while (!((ch=getchar())>='0'&&ch<='9'));
    a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
void addedge(int x,int y) {
    to[++tot]=y; nxt[tot]=g[x]; g[x]=tot;
    to[++tot]=x; nxt[tot]=g[y]; g[y]=tot;
}
void dfs(int x,int fat) {
    fa[x]=fat;
    for (int k=g[x];k;k=nxt[k]) if (to[k]!=fat) {
        dfs(to[k],x);
        if (num[to[k]]>num[w[x]]) w[x]=to[k];
        num[x]+=num[to[k]];
    } num[x]++;
}
void dfs2(int x,int tail) {
    dfn[x]=++df; top[x]=tail;
    if (w[x]) dfs2(w[x],tail);
    for (int k=g[x];k;k=nxt[k]) {
        if (to[k]==fa[x]||to[k]==w[x]) continue;
        dfs2(to[k],to[k]);
    }
}
void build(int i,int l,int r) {
    if (l==r) {
        f[i]=1;
        return;
    } int mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    f[i]=f[i<<1]+f[i<<1|1];
}
void change(int i,int l,int r,int x) {
    if (l==r) {
        f[i]=0;
        return;
    } int mid=(l+r)>>1;
    if (x<=mid) change(i<<1,l,mid,x);
    else change(i<<1|1,mid+1,r,x);
    f[i]=f[i<<1]+f[i<<1|1];
}
int ask(int i,int l,int r,int x,int y) {
    if (x<=l&&y>=r) return f[i];
    int mid=(l+r)>>1,ans=0;
    if (x<=mid) ans+=ask(i<<1,l,mid,x,y);
    if (y>mid) ans+=ask(i<<1|1,mid+1,r,x,y);
    return ans;
}
int query(int x) {
    int ans=0;
    while (top[x]!=1) ans+=ask(1,1,n,dfn[top[x]],dfn[x]),x=fa[top[x]];
    ans+=ask(1,1,n,1,dfn[x])-1;
    return ans;
}
int main() {
    int i,x,y;
    for (read(n),i=1;i<n;i++) {
        read(x); read(y);
        addedge(x,y);
    }
    dfs(1,1); dfs2(1,1);
    build(1,1,n);
    for (read(m),i=1;i<n+m;i++) {
        scanf("%s",&s);
        if (s[0]=='A') {
            read(x); read(y);
            if (fa[y]!=x) swap(x,y);
            change(1,1,n,dfn[y]);
        } else if (s[0]=='W') {
            read(x);
            printf("%d\n",query(x));
        }
    }
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
struct node{
    int id,pri,st,tm;
    friend bool operator < (node a,node b) {return a.pri<b.pri||(a.pri==b.pri&&a.st>b.st);}
}t,w;
priority_queue<node> q,q1;
int now;
void print() {
    node t=q.top(),w; q.pop();
    printf("%d %d\n",t.id,now+t.tm);
    now+=t.tm;
}
int main() {
    while (~scanf("%d%d%d%d",&t.id,&t.st,&t.tm,&t.pri)) {
        if (q.empty()) {
            q.push(t);
            now=max(t.st,now);
        } else {
            if (t.st>=now) while (!q.empty()) {
                w=q.top();
                if (now+w.tm<=t.st) print();
                else {
                    w.tm-=t.st-now;
                    q.pop();
                    q.push(w);
                    break;
                }
            } q.push(t);
            now=max(t.st,now);
        }
    } while (!q.empty()) print();
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=1000100;
vector<int >v[70];
vector<int >g[N];
int n,m,tot,b[N];
int f[N],num,ans=infi,last;
void read(int &a) {
    char ch; while (!((ch=getchar())>='0'&&ch<='9'));
    a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
int check(int l,int r,int x) {
    int mid;
    while (l<r) {
        mid=(l+r)>>1;
        if (x<=b[mid]) r=mid;
        else l=mid+1;
    } return r;
}
int main() {
    int i,j,sz,x,y;
    read(n); read(m);
    for (i=1;i<=m;i++) {
        read(x);
        for (j=1;j<=x;j++) {
            read(y);
            b[++tot]=y;
            v[i].push_back(y);
        }
    }
    sort(b+1,b+1+n);
    for (i=1;i<=m;i++) {
        sz=v[i].size();
        for (j=0;j<sz;j++) {
            x=check(1,n,v[i][j]);
            g[x].push_back(i);
        }
    } last=1; b[0]=-1;
    for (i=1;i<=n;i++) {
        if (b[i]==b[i-1]) continue;
        sz=g[i].size();
        for (j=0;j<sz;j++) {
            if (f[g[i][j]]==0) num++;
            f[g[i][j]]++;
        } while (num==m&&last<i) {
            ans=min(ans,b[i]-b[last]);
            sz=g[last].size();
            for (j=0;j<sz;j++) {
                f[g[last][j]]--;
                if (f[g[last][j]]==0) num--;
            } last++;
        }
    } cout<<ans<<endl;
    return 0;
}
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const int mod=1000000007;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=2097152;
const int M=30;
int S,f[N],d[N],t[M],h[M],s[M];
int n,H,ans=-1;
bool b[N];
void Max(int &x,int y) {if (x<y) x=y;}
int main() {
    int i;
    scanf("%d%d",&n,&H);
    for (i=0;i<n;i++) scanf("%d%d%d",&h[i],&t[i],&s[i]);
    f[0]=infi;
    for (S=0;S<(1<<n);S++) {
        for (i=0;i<n;i++) if (!(S&(1<<i))) {
            d[S^(1<<i)]=d[S]+h[i];
            if (f[S]>=t[i]) {
                Max(f[S^(1<<i)],min(f[S]-t[i],s[i]));
                if (d[S^(1<<i)]>=H) Max(ans,f[S^(1<<i)]);
            }
        }
    } if (ans!=-1) cout<<ans<<endl;
    else puts("Mark is too tall");
    return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter