厉害了
by zhaolala @ 2016-11-09 19:59:01
+1
```cpp
#include<cstdio>
#include<cstring>
#define N 15010
using namespace std;
struct P
{
int id,arr,ret,pri;
void clear() {id=arr=ret=pri=0;}
bool operator < (P b)
{
P a=*this;
return a.pri==b.pri? a.arr<b.arr :a.pri<b.pri;
}
}heap[N<<2];
int lst=0,t=1;
int min(int a,int b) {return a<b?a:b;}
void swap(P &a,P &b) {P t=a;a=b;b=t;}
void test()
{
printf("test:\n");
printf("t:%d\n",t);
for(int i=1;i<=lst;i++)
printf("%d %d %d %d\n",heap[i].id,heap[i].arr,heap[i].ret,heap[i].pri);
printf("\n");
}
void push_up(int pos)
{
while(pos>1 && heap[pos/2]<heap[pos])
{
swap(heap[pos],heap[pos/2]);
pos>>=1;
}
}
void push_down(int pos)
{
while(pos*2<=lst)
{
int p=pos<<1;
if(p+1<=lst && heap[p]<heap[p+1]) p=p+1;
if(heap[pos]<heap[p]) {swap(heap[pos],heap[p]); pos=p;}
else break;
}
}
void push(P a)
{
heap[++lst]=a;
push_up(lst);
}
void pop()
{
heap[1].clear();
swap(heap[1],heap[lst--]);
push_down(1);
}
int main()
{
P a;
while(scanf("%d %d %d %d",&a.id,&a.arr,&a.ret,&a.pri)==4)
{
if(lst==0) {push(a);t=a.arr; continue;}
while(heap[1].pri>a.pri && t<a.arr && lst>0)
{
int tmp=min(heap[1].ret,a.arr-t);
printf("?%d ?",tmp);
heap[1].ret-=tmp; t+=tmp;
if(heap[1].ret==0) {printf("%d %d\n",heap[1].id,t); pop();}
}
if(lst>0)
{
int tmp=min(heap[1].ret,a.arr-t);
printf("!%d %d %d!",tmp,heap[1].ret,a.arr-t);
heap[1].ret-=tmp; t+=tmp;
}
push(a);
test();
}
return 0;
}
```
/\*1 1 5 3
2 10 5 1
3 12 7 2
4 20 2 3
5 21 9 4
6 22 2 4
7 23 5 2
8 24 2 4
\*/
by functionendless @ 2017-05-31 13:23:30
```cpp
#include<cstdio>//答案->书->练习册 S N M
#include<cstring>
#include<queue>
#define INF 1e9
using namespace std;
int N,M,S,m,s,t,ans=0;
int head[30010],nxt[200010],to[200010],cap[200010],cnt=-1;
int step[30010]; bool used[30010];
inline void test()
{
for(int i=s;i<=t;i++)
{
printf("%d:\n",i);
for(int j=head[i];j!=-1;j=nxt[j])
printf("{%d %d}\n",to[j],cap[j]);
}
}
inline void adde(int x,int y,int c)
{
nxt[++cnt]=head[x]; to[cnt]=y; cap[cnt]=c; head[x]=cnt;
nxt[++cnt]=head[y]; to[cnt]=x; cap[cnt]=0; head[y]=cnt;
}
inline void init()
{
for(int i=1;i<=S;i++) adde(s ,i,INF);
for(int i=1;i<=M;i++) adde(i+S+N,t,INF);
}
bool BFS()
{
memset(step,63,sizeof(step));
queue<int> que;
step[s]=0; que.push(s); used[s]=1;
while(!que.empty())
{
int p=que.front(); que.pop();
for(int i=head[p]; i!=-1; i=nxt[i])
if(!used[to[i]] && cap[to[i]]) {step[to[i]]=step[p]+1; used[to[i]]=1;}
}
for(int i=s;i<=t;i++) printf("%d ",step[i]);
if(step[t]==step[t+1]) return false;
return true;
}
int dfs(int u,int flow)
{
if(u==t || flow==0) return flow;
for(int i=head[u];i!=-1;i=nxt[i])
if(cap[to[i]]>0 && step[u]+1==step[to[i]])
{
int f=dfs(to[i],min(cap[to[i]],flow));
if(f)
{
cap[to[i]]-=f; cap[to[i^1]]+=f; return f;
}
}
}
void Max_flow()
{
//printf("?");
while(BFS())
{
int tmp=dfs(s,INF);
while(tmp!=0) {ans+=tmp; tmp=dfs(s,INF);}
}
}
int main()
{
int i,x,y;
memset(head,-1,sizeof(head));
scanf("%d %d %d",&N,&M,&S); s=0; t=N+M+S+1;
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);//书 册
adde(x+S,y+S+N,1);
}
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);//书 答
adde(y,x+S,1);
}
init();
test();
Max_flow();
printf("%d",ans);
return 0;
}
```
/\*5 3 4
5
4 3
2 2
5 2
5 1
5 3
5
1 3
3 1
2 2
3 3
4 3\*/
by functionendless @ 2017-06-08 13:27:49
```cpp
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#define INF 1e9
#define N 110
#define M 110
#define S 100010
using namespace std;
int n,m,ans=0;
int head[N+M+M],nxt[S],to[S],cap[S];
int step[N+M+M],cur[N+M+M],s=0,t; int cnt=-1;
bool used[N+M+M];
void adde(int x,int y,int c)
{
nxt[++cnt]=head[x]; to[cnt]=y; cap[cnt]=c; head[x]=cnt;
nxt[++cnt]=head[y]; to[cnt]=x; cap[cnt]=0; head[y]=cnt;
}
void init()
{
for(int i=1;i<=n;i++) adde(s,i,1);
for(int i=n+1;i<=n+m;i++) adde(i,i+m,1);
for(int i=n+m+1;i<=n+m+m;i++) adde(i,t,1);
}
bool BFS()
{
queue<int> que;
memset(used,0,sizeof(used)); memset(step,63,sizeof(step));
que.push(s); used[s]=1; step[s]=0;
while(!que.empty())
{
int p=que.front(); que.pop();
for(int i=head[p];i!=-1;i=nxt[i])
if(!used[to[i]] && cap[i])
{
used[to[i]]=1;
step[to[i]]=step[p]+1;
que.push(to[i]);
}
}
if(step[t]==step[t+1]) return false;
return true;
}
int dfs(int u,int flow)
{
if(u==t || flow==0) return flow;
for(int &i=cur[u];i!=-1;i=nxt[i])
if(cap[i] && step[to[i]]==step[u]+1)
{
int f=dfs(to[i],min(cap[i],flow));
if(f) {cap[i]-=flow; cap[i^1]+=flow; return f;}
}
return 0;
}
void dinic()
{
while(BFS())
{
printf("?");
for(int i=s;i<=t;i++) cur[i]=head[i];
int tmp=dfs(s,INF);
while(tmp) {ans+=tmp; dfs(s,INF);}
}
}
int main()
{
memset(head,-1,sizeof(head));
int i,j,x,y; t=n+m+1;
scanf("%d %d",&n,&m);
scanf("%d %d",&x,&y);
while(x!=-1 && y!=-1)
{
adde(x,y+m,1);
scanf("%d %d",&x,&y);
}
init();
dinic();
printf("%d\n",ans);
return 0;
}
```
by functionendless @ 2017-06-09 13:09:50
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#define N 100010
#define ll long long
using namespace std;
ll sum[N<<2];
int n,m,M;
void test() {for(int i=1;i<=M+n;i++) printf("%d ",sum[i]); printf("\n");}
void build_tre()
{
for(M=1;M<n;M<<=1); M-=1;
for(int i=M+1;i<=M+n;i++) scanf("%lld",&sum[i]);
}
void update(int l,int r,int c)
{
ll tmp; int s,t;
for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1)
{
if(!(l&1)) sum[l^1]+=c;
if( r&1 ) sum[r^1]+=c;
tmp=min(sum[l],sum[l^1]); sum[l]-=tmp; sum[l^1]-=tmp; sum[l>>1]+=tmp;
tmp=min(sum[r],sum[r^1]); sum[r]-=tmp; sum[r^1]-=tmp; sum[r>>1]+=tmp;
}
for(;l!=1;l>>=1) {tmp=min(sum[l],sum[l^1]); sum[l]-=tmp; sum[l^1]-=tmp; sum[l>>1]+=tmp;}
}
ll query(int l,int r)
{
ll ans=0;
if(l!=r)
for(l+=M,r+=M;l^r^1;l>>=1,r>>=1)
{
ans+=sum[l]+sum[r];
if(!(l&1)) ans+=sum[l^1];
if(r&1) ans+=sum[r^1];
}
ans+=sum[l]+sum[r];
while(l>1) ans+=sum[l>>=1];
return ans;
}
int main()
{
scanf("%d %d",&n,&m);
build_tre(); test();
while(m--)
{
int type,x,y,c;
scanf("%d",&type);
if(type==1)
{
scanf("%d %d %d",&x,&y,&c);
update(x,y,c);
}
else
{
scanf("%d %d",&x,&y);
printf("%lld\n",query(x,y));
}
test();
}
return 0;
}
```
by functionendless @ 2017-06-13 13:27:59
```cpp
#include<cstdio>
#include<cstring>
using namespace std;
int c,v0,v1,a,l,ans=1;
int main()
{
int v,i,t;
scanf("%d %d %d %d %d",&c,&v0,&v1,&a,&l);
if(a!=0) t=(v1-v0)/a; else t=10000000;
c-=v0; v=v0;
for(i=1;c>0 && i<=t;i++)
{
ans++;
v+=a;
c=c-v+l;
}
if(c<=0) {printf("%d\n",ans); return 0;}
v=v1;
while(c>0)
{
c=c-v+l;ans++;
}
printf("%d\n",ans);
return 0;
}
```
by functionendless @ 2017-06-28 06:40:57
#include<cstdio>//0->dec 1->inc f[i][0]->a[i] put on first row's best solution on second row
```cpp
#include<cstring>
#define N 1000010
using namespace std;
int a[N],n,f[N][2],pa[N];//0 done up how down 1 !
bool judge(int t1,int t2)
{
memset(f,-1,sizeof(f)); memset(pa,-1,sizeof(pa));
f[1][1]=t1 ? 0 : n+1; f[1][0]=t2 ? 0 : n+1;
for(i=2;i<=n;i++)
{
if(f[i-1][0]!=-1)
{
if((a[i]<f[i-1][1]) && t1==0) //(a[i]<a[i-1]) ^ t1
{pa f[i][0]=f[i-1][0];}
if((a[i]<f[i-1][0]) && t2==0) //(a[i]<a[]) ^ t2
}
if(f[i-1][1]!=-1)
{
}
}
}
int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
for(i=0;i<2;i++)
for(j=0;j<2;j++)
if(judge(i,j))
return 0;
puts("Fail");
return 0;
}
```
by functionendless @ 2017-06-28 21:40:09
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#define pb push_back
#define N 100010
using namespace std;
int n,q,c[N],fa[N];
vector<int> G[N],son[N];
void build_tre(int u,int f)
{
int l=G[u].size();
for(i=0;i<l;i++)
if(G[u][i]!=f)
{
int to=G[u][i];
son[u].pb(to);
fa[to]=u;
build_tre(to,u);
}
}
int main()
{
int i,j,x,y;
scanf("%d %d",&n,&q);
for(i=1;i<=n;i++) scanf("%d",&c[i]);
for(i=1;i<n;i++)
{
scanf("%d %d",&x,&y);
G[x].pb(y); G[y].pb(x);
}
build_tre(1,0);
return 0;
}
```
by functionendless @ 2017-06-29 21:26:45
```cpp
#include<cstdio>
#include<cstring>
#include<queue>
#define int long long
#define N 100010
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define F first
#define S second
#define left lc,l,r
#define right rc,l,r
#define mid ((s[u]+e[u])>>1)
using namespace std;
int n,m,S;
int s[N<<2],e[N<<2],lc[N<<2],rc[N<<2];
int dis[N<<2],key[N];
int head[N<<2],nxt[N<<2],to[N<<2],v[N<<2],lst=0;
bool used[N<<2];
inline void adde(int x,int y,int c) {nxt[++lst]=head[x]; to[lst]=y; v[lst]=c; head[x]=lst;}
void build_tre(int u,int l,int r,int t)
{
if(u!=1) if(t) adde(u>>1,u,0); else adde(u,u>>1,0);
s[u]=l; e[u]=r;
if(s[u]==e[u]) {key[s[u]]=u;return;}
build_tre(lc,l,mid); build_tre(rc,mid+1,r);
}
void update(int u,int l,int r,int v,int c,int t)
{
if(l<=s[u] && e[u]<=r) {puts("?"); t ? adde(key[v],u,c) : adde(u,key[v],c); return;}
if(mid>=l) update(left,v,c,t);
if(mid< r) update(right,v,c,t);
}
void SPFA()
{
queue<int> que; memset(dis,63,sizeof(dis));
que.push(key[S]); used[key[S]]=1; dis[key[S]]=0;
while(!que.empty())
{
int p=que.front(); que.pop();
for(int i=head[p];i;i=nxt[i])
{
//printf("?%d?",p);
if(dis[to[i]]>dis[p]+v[i])
{
dis[to[i]]=dis[p]+v[i];
if(!used[to[i]]) {used[to[i]]=1; que.push(to[i]);}
}
}
used[p]=0;
}
}
void test()
{
for(int i=1;i<=7;i++)
{
printf("%I64d: ",i);
for(int j=head[i]; j;j=nxt[j]) printf("(%I64d %I64d) ",to[j],v[j]);
puts("");
}
}
main()
{
int i,j;
scanf("%I64d %I64d %I64d",&n,&m,&S);
build_tre(1,1,n,1); build_tre(1,1,n,0);
for(i=1;i<=m;i++)
{
int type,x,y,v,l,r,c;
scanf("%I64d",&type);
if(type==1)
{
scanf("%I64d %I64d %I64d",&x,&y,&c);
update(1,y,y,x,c,1);
}
else if(type==2)
{
scanf("%I64d %I64d %I64d %I64d",&v,&l,&r,&c);
update(1,l,r,v,c,1);
}
else if(type==3)
{
scanf("%I64d %I64d %I64d %I64d",&v,&l,&r,&c);
update(1,l,r,v,c,0);
}
}
SPFA();
test();
for(i=1;i<=n;i++) printf("%I64d ",dis[key[i]]==dis[0] ? -1 : dis[key[i]]);
return 0;
}
```
by functionendless @ 2017-07-03 15:32:07
```cpp
#include<cstdio>
#include<cstring>
#define N 100010
#define NN N<<2
#define lc (u<<1)
#define rc (lc+1)
#define left lc,x
#define right rc,x
#define mid ((s[u]+e[u])>>1)
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
int n,m;
char ch[20];
int s[NN],e[NN],l1[NN],r1[NN],l2[NN],r2[NN],L[NN],R[NN];
void build_tre(int u,int ll,int rr)
{
l1[u]=l2[u]=s[u]=ll;r1[u]=r2[u]=e[u]=rr; L[u]=rr+1; R[u]=ll-1;
if(ll==rr) return ;
build_tre(lc,ll,mid); build_tre(rc,mid+1,rr);
}
void update(int u,int seg,int type)
{
}
void clear(int u,int x,int y)
{
}
int main()
{
int i,j,T;
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&n,&m);
build_tre(1,1,n);
for(i=1;i<=m;i++)
{
int x,y,ans=0;
scanf("%s",ch);
if(ch[0]=='D')
{
scanf("%d",&x);
ans=update(1,x,1);
if(ans) printf("%d,let's fly\n",ans);
else printf("fly with yourself\n");
}
else if(ch[0]=='N')
{
scanf("%d",&x);
ans=update(1,x,2);
if(ans) printf("%d,don't put my gezi\n",ans);
else printf("wait for me\n");
}
else if(ch[0]=='S')
{
scanf("%d %d",&x,&y);
clear(1,x,y);
puts("I am the hope of chinese chengxuyuan!!");
}
}
}
return 0;
}
```
by functionendless @ 2017-07-07 15:20:18