Submission #876200

#TimeUsernameProblemLanguageResultExecution timeMemory
876200winter0101Harvest (JOI20_harvest)C++14
100 / 100
2158 ms313288 KiB
#include<bits/stdc++.h> using namespace std; #define all(fl) fl.begin(),fl.end() #define pb push_back #define fi first #define se second #define for1(i,j,k) for(int i=j;i<=k;i++) #define for2(i,j,k) for(int i=j;i>=k;i--) #define for3(i,j,k,l) for(int i=j;i<=k;i+=l) #define lb lower_bound #define ub upper_bound #define sz(a) (int)a.size() #define pii pair<int,int> #define pli pair<long long,int> #define gcd __gcd #define lcm(x,y) x*y/__gcd(x,y) #define lastbit(i) __builtin_ctz(i) const int maxn=2e5+9; int a[maxn],b[maxn]; struct BIT{ vector<long long>bit; int n; void resz(int _n){ n=_n; bit.clear(); bit.resize(n+1); for1(i,1,n)bit[i]=0; } void add(int pos,long long val){ for(;pos<=n;pos+=(pos-(pos&(pos-1))))bit[pos]+=val; } void del(int pos){ for (;pos<=n;pos+=(pos-(pos&(pos-1))))bit[pos]=0; } long long get(int pos){ long long sum=0; if (pos<0)return 0; for(;pos>=1;pos-=(pos-(pos&(pos-1))))sum+=bit[pos]; return sum; } long long get(int l,int r){ if (l>r)return 0; return get(r)-get(l-1); } }; int id[maxn*2]; #define pil pair<int,long long> vector<pil>g[maxn*2];//edge int gr[maxn];//group of cycle int deg[maxn*2];//deg to remove bool vis[maxn];//travel in cycle long long dep[maxn];//dep in cycle int num=0; vector<int>cc[maxn];//vertice in each cycle long long len[maxn]; long long dfs(int u){//dfs cycle gr[u]=num; cc[num].pb(u); long long ans=0; vis[u]=1; for (auto v:g[u]){ ans+=v.se; if (!vis[v.fi]){ vis[v.fi]=1; dep[v.fi]=dep[u]+v.se; ans+=dfs(v.fi); } } return ans; } vector<pil>rg[maxn*2];//reverse edge long long d[maxn*2];//dep in tree vector<pil>h[maxn*2];//apple int in[maxn*2],out[maxn*2]; int rootincyc[maxn*2]; int tme=0; pil query[maxn]; int n,m; void redfs(int u,int root){ if (u>n)h[root].pb({u,d[u]}); rootincyc[u]=root; in[u]=++tme; for (auto v:rg[u]){ if (deg[v.fi])continue; d[v.fi]=d[u]+v.se; redfs(v.fi,root); } out[u]=tme; } struct line{ int type;//update or answer int u;//type of apple of vertice long long val;//time of dep int idx; bool operator < (const line &p)const { if (val==p.val)return type<p.type; return val<p.val; } }; struct queryt2{ int u; long long k; int id; }; vector<line>quest[maxn]; vector<queryt2>quet[maxn]; long long cum(int u,int v){ if (dep[v]>=dep[u])return dep[v]-dep[u]; return len[gr[u]]-(dep[u]-dep[v]); } long long answer[maxn]; //solve for cycle long long du; long long value[maxn*2]; long long value_mod[maxn*2]; int pos[maxn]; int revpos[maxn*2]; vector<int>arr[maxn*4]; BIT cnt[maxn*4]; BIT st[maxn*4]; int pos_update[maxn*2][20]; int dep_tree[maxn*4]; void build(int id,int l,int r){ arr[id].clear(); arr[id].resize(r-l+1+1),st[id].resz(r-l+1),cnt[id].resz(r-l+1); int dd=dep_tree[id]; for1(i,1,r-l+1){ arr[id][i]=pos[i+l-1]; } sort(arr[id].begin()+1,arr[id].begin()+1+r-l+1,[](int i,int j){ return value[i]<value[j]; }); for1(i,1,r-l+1)pos_update[arr[id][i]][dd]=i; if (l==r)return; int mid=(l+r)/2; dep_tree[id*2]=dep_tree[id*2+1]=dep_tree[id]+1; build(id*2,l,mid); build(id*2+1,mid+1,r); } void update(int id,int l,int r,int u){ if (revpos[u]<l||revpos[u]>r)return; long long val=(value[u]-value_mod[u])/du; int dd=dep_tree[id]; st[id].add(pos_update[u][dd],val); cnt[id].add(pos_update[u][dd],1); if (l==r)return; int mid=(l+r)/2; update(id*2,l,mid,u); update(id*2+1,mid+1,r,u); } long long get(int id,int l,int r,int u,int v,long long val,bool fl){ if (l>v||r<u||u>v)return 0; if (u<=l&&r<=v){ int l1=1,r1=r-l+1,as=-1; while (l1<=r1){ int mid=(l1+r1)/2; if (value[arr[id][mid]]<=val){ as=mid; l1=mid+1; } else r1=mid-1; } if (as==-1)return 0; long long nval=((val%du)+du)%du; long long mval=(val-nval)/du; long long xxx=cnt[id].get(as); return xxx*mval-st[id].get(as)+fl*xxx; } int mid=(l+r)/2; return get(id*2,l,mid,u,v,val,fl)+get(id*2+1,mid+1,r,u,v,val,fl); } long long l,c; long long cal(int i,int j){ if (a[j]>=a[i])return a[j]-a[i]; else return l-(a[i]-a[j]); } // /* Nhan xet: dung duoc do thi mat troi n+m dinh n+m canh voi nhung dinh khong thuoc chu trinh thi co the tinh bang sweepline voi nhung dinh thuoc chu trinh, ta co goi h[u] la nhung qua tao trong cay u d[u] la do sau cua 1 thang trong cay dep[u] la do sau cua 1 dinh trong chu trinh voi viec chon dinh nao do thuoc chu trinh lam goc thi de tinh cac dinh ma thuoc cycle goi dinh do la x va thoi gian la k length la do dai chu trinh ta se can dem tong (v la apple thuoc chu trinh, d[v]<=k,v la con cua u) (k-d[v])/length+[(k-d[v])%length>=d(u,x)] (d(u,x) la khoang cach tu u den x tren chu trinh) voi subtask 2 thi khong can quan tam k-d[v] vi k>=1e15 nen co the giai trong nlog^2 subtask 3 neu tiep tuc lam the thi se mat nlog^3 nen ta can co nhan xet (k-d[v])/length+[(k-d[v])%length>=d(u,x)]=((k-d[v]-d(u,x))/length+1)*[k-d[v]-d(u,x)>=0] chung minh 0<=d(u,x)<length luu y cac phep chia nay la phep lam tron xuong neu k-d[v]>0 k-d[v]<d(u,x) thi (k-d[v])/length=0 nen luon can k-d[v]>=d(u,x) goi p=k-d[v] mod length, q=d(u,x) mod length,p1=k-d[v],q1=d(u,x) neu p>=q thi (p1-q1)/length thoa man vi p1/length=(p1-q1)/length va p1>=q1 neu p<q thi (p1-q1)/length=(p1/length-1) va tuong tu ta lai thoa man nen ta co the dua ve tinh tong ((k-d[v]-d(u,x))/length+1)*[k-d[v]-d(u,x)>=0] de kiem soat d(u,x) ta co the sweepline u 2 lan, luu 1 cay segmentree, moi node la bit quan li cac phan tu tu l->r, segment tree quan li theo modulo va moi node sort theo value tu do dua dpt ve nlog^2 */ signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); //freopen("temp.INP","r",stdin); //freopen("temp.OUT","w",stdout); cin>>n>>m>>l>>c; for1(i,1,n)cin>>a[i]; for1(i,1,n)id[i]=i; for1(i,n+1,2*n)id[i]=id[i-n]; for1(i,1,n){ long long w=(c/l)*l; int l1=i+1,r1=i+n,ans=-1; while (l1<=r1){ int mid=(l1+r1)/2; if (cal(id[mid],i)>=(c%l)){ ans=mid; l1=mid+1; } else r1=mid-1; } if (ans==-1)w+=l,ans=i; else w+=cal(id[ans],i); g[i].pb({id[ans], w}); deg[id[ans]]++; } for1(i,1,m){ cin>>b[i]; int l1=1,r1=n,ans=n; while (l1<=r1){ int mid=(l1+r1)/2; if (a[mid]<=b[i]){ ans=mid; l1=mid+1; } else r1=mid-1; } if (a[ans]<=b[i])g[i+n].pb({ans,b[i]-a[ans]}); else g[i+n].pb({ans,l-(a[ans]-b[i])}); } queue<int>t; for1(i,1,n){ if (!deg[i]){ t.push(i); } } while (!t.empty()){ auto u=t.front(); t.pop(); for (auto v:g[u]){ deg[v.fi]--; if (!deg[v.fi]){ t.push(v.fi); } } } vector<long long>cyc; num=0; for1(i,1,n){ if (!deg[i]||vis[i])continue; //detect cycle num++; len[num]=dfs(i); } for1(i,1,n+m){ for (auto v:g[i]){ rg[v.fi].pb({i,v.se}); } } for1(i,1,n){ if (deg[i]){ redfs(i,i); } } int q; cin>>q; for1(i,1,q){ cin>>query[i].fi>>query[i].se; if (!deg[query[i].fi]){ quest[rootincyc[query[i].fi]].pb({2,query[i].fi,query[i].se+d[query[i].fi],i}); } else { quet[query[i].fi].pb({query[i].fi,query[i].se,i}); } } BIT bit; bit.resz(n+m); for1(i,1,n){ if (deg[i]){ vector<line>sol; for (auto v:h[i]){ sol.pb({1,v.fi,v.se,0}); } for (auto v:quest[i]){ sol.pb(v); } vector<line>().swap(quest[i]); sort(all(sol)); for (auto v:sol){ if (v.type==1){ bit.add(in[v.u],1); } else { answer[v.idx]=bit.get(in[v.u],out[v.u]); } } for (auto v:sol){ if (v.type==1)bit.del(in[v.u]); } } } //d dep in tree //dep dep in cycle for1(i,1,num){ du=len[i]; int nlen=0; for(auto u:cc[i]){ for (auto v:h[u]){ value[v.fi]=(v.se-dep[u]); value_mod[v.fi]=((value[v.fi]%du)+du)%du; pos[++nlen]=v.fi; } } if (nlen==0)continue; sort(pos+1,pos+nlen+1,[](int x,int y){ return value_mod[x]<value_mod[y]; }); for1(j,1,nlen){ revpos[pos[j]]=j; } build(1,1,nlen); for(auto u:cc[i]){ for (auto v:h[u])update(1,1,nlen,v.fi); for (auto v:quet[u]){ int l1=1,r1=nlen,p=0; long long val=v.k-dep[v.u]; long long nval=((val%du)+du)%du; while (l1<=r1){ int mid=(l1+r1)/2; if (value_mod[pos[mid]]<=nval){ p=mid; l1=mid+1; } else r1=mid-1; } answer[v.id]+=get(1,1,nlen,1,p,val,1)+get(1,1,nlen,p+1,nlen,val,0); } } nlen=0; for(auto u:cc[i]){ for (auto v:h[u]){ value[v.fi]=(v.se-dep[u]); value_mod[v.fi]=((value[v.fi]%du)+du)%du; pos[++nlen]=v.fi; } } sort(pos+1,pos+nlen+1,[](int x,int y){ return value_mod[x]<value_mod[y]; }); for1(j,1,nlen){ revpos[pos[j]]=j; } build(1,1,nlen); reverse(all(cc[i])); for(auto u:cc[i]){ for (auto v:quet[u]){ int l1=1,r1=nlen,p=0; long long val=v.k-dep[v.u]-len[i]; long long nval=((val%du)+du)%du; while (l1<=r1){ int mid=(l1+r1)/2; if (value_mod[pos[mid]]<=nval){ p=mid; l1=mid+1; } else r1=mid-1; } answer[v.id]+=get(1,1,nlen,1,p,val,1)+get(1,1,nlen,p+1,nlen,val,0); } for (auto v:h[u]){ update(1,1,nlen,v.fi); } } } // for1(i,1,q){ if (!deg[query[i].fi])cout<<answer[i]<<'\n'; else cout<<answer[i]<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...