제출 #942285

#제출 시각아이디문제언어결과실행 시간메모리
942285MilosMilutinovic수확 (JOI20_harvest)C++14
25 / 100
2889 ms264216 KiB
#include<bits/stdc++.h> #define pb push_back #define fi first #define se second #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef long double ld; template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;} template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;} ll readint(){ ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,l,c,q,T,tsz; int a[200005],b[200005],prv[200005],deg[200005],rt[400005],fenw[400005],dfn[200005],dfo[200005],cnt[10000005],ls[10000005],rs[10000005],root[400005]; ll d[200005],sum[10000005]; vector<pair<ll,int>> qs[200005]; vector<array<ll,4>> ev; vector<ll> my[200005]; ll ans[200005]; vector<int> topo,ch[200005]; bool oncyc[200005]; ll calc(ll x){return x>=c?x:((c-x+l-1)/l)*1ll*l+x;} ll divb(ll x,ll y){return x>=0?x-x%y:x-((y+(x%y))%y);} int getprv(int x){ int d=c%l; if(a[1]<=x-d){ int l=1,r=n,p=1; while(l<=r){ int mid=(l+r)/2; if(a[mid]<=x-d) l=mid+1,p=mid; else r=mid-1; } return p; }else{ int l=1,r=n,p=1; while(l<=r){ int mid=(l+r)/2; if(x+::l-a[mid]>=d) l=mid+1,p=mid; else r=mid-1; } return p; } } void change(int p,int v){ for(;p<400005;p|=p+1) fenw[p]+=v; } int ask(int p){ int v=0; for(;p>=0;p=(p&(p+1))-1) v+=fenw[p]; return v; } void dfs1(int x,ll d){ dfn[x]=++T; for(auto&p:my[x]) ev.pb({d+p,0,dfn[x],0}); for(auto&p:qs[x]) ev.pb({p.fi+d,1,x,p.se}); for(auto&p:my[x]) my[rt[x]].pb(p+d); for(int v:ch[x]){ rt[v]=rt[x]; ll w=calc(a[x]<=a[v]?a[v]-a[x]:a[v]+l-a[x]); dfs1(v,d+w); } dfo[x]=T; } void modifyy(int&id,int l,int r,int p,ll v){ if(!id) id=++tsz,cnt[id]=sum[id]=ls[id]=rs[id]=0; sum[id]+=v; cnt[id]++; if(l==r) return; int mid=(l+r)/2; if(p<=mid) modifyy(ls[id],l,mid,p,v); else modifyy(rs[id],mid+1,r,p,v); } void modifyx(int x,int y,ll v){ for(;x<400005;x|=(x+1)) modifyy(root[x],0,400005,y,v); } pair<ll,int> queryy(int id,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr) return mp(sum[id],cnt[id]); int mid=(l+r)/2; if(qr<=mid) return queryy(ls[id],l,mid,ql,qr); else if(ql>mid) return queryy(rs[id],mid+1,r,ql,qr); pair<ll,int> lv=queryy(ls[id],l,mid,ql,qr); pair<ll,int> rv=queryy(rs[id],mid+1,r,ql,qr); return mp(lv.fi+rv.fi,lv.se+rv.se); } pair<ll,int> queryx(int x1,int x2,int y1,int y2){ pair<ll,int> ret=mp(0ll,0); for(int x=x2;x>=0;x=(x&(x+1))-1){ pair<ll,int> f=queryy(root[x],0,400005,y1,y2); ret.fi+=f.fi; ret.se+=f.se; } for(int x=x1-1;x>=0;x=(x&(x+1))-1){ pair<ll,int> f=queryy(root[x],0,400005,y1,y2); ret.fi-=f.fi; ret.se-=f.se; } return ret; } void clrx(int x){ for(;x<400005;x|=(x+1)) root[x]=0; } int main(){ n=readint(); m=readint(); l=readint(); c=readint(); for(int i=1;i<=n;i++) a[i]=readint(); for(int i=1;i<=m;i++) b[i]=readint(); q=readint(); for(int i=1;i<=q;i++){ int v=readint(); ll t=readint(); qs[v].pb(mp(t,i)); } for(int i=1;i<=n;i++) prv[i]=getprv(a[i]); for(int i=1;i<=m;i++){ int idx; if(a[1]<=b[i]){ int l=1,r=n; while(l<=r){ int mid=(l+r)/2; if(a[mid]<=b[i]) idx=mid,l=mid+1; else r=mid-1; } }else idx=n; my[idx].pb((b[i]-a[idx]+l)%l); } for(int i=1;i<=n;i++) deg[prv[i]]++; for(int i=1;i<=n;i++) if(deg[i]==0) topo.pb(i); for(int i=0;i<(int)topo.size();i++){ int v=topo[i]; deg[prv[v]]--; if(deg[prv[v]]==0) topo.pb(prv[v]); } for(int i=1;i<=n;i++) oncyc[i]=true; for(int i:topo) oncyc[i]=false; for(int i=1;i<=n;i++) ch[prv[i]].pb(i); for(int i=1;i<=n;i++){ if(oncyc[i]||!oncyc[prv[i]]) continue; rt[i]=prv[i]; ll w=calc(a[prv[i]]<=a[i]?a[i]-a[prv[i]]:a[i]+l-a[prv[i]]); T=0; ev.clear(); dfs1(i,w); sort(ev.begin(),ev.end()); for(auto&p:ev){ if(p[1]==0){ change(p[2],1); }else{ ans[p[3]]=ask(dfo[p[2]])-ask(dfn[p[2]]-1); } } for(auto&p:ev) if(p[1]==0) change(p[2],-1); } for(int i=1;i<=n;i++){ if(!oncyc[i]) continue; vector<int> f; int ver=i; while(oncyc[ver]){ f.pb(ver); oncyc[ver]=false; ver=prv[ver]; } int sz=(int)f.size(); d[0]=0; for(int i=1;i<sz;i++){ ll w=calc(a[f[i]]<=a[f[i-1]]?a[f[i-1]]-a[f[i]]:a[f[i-1]]+l-a[f[i]]); d[i]=d[i-1]+w; } ll len=d[sz-1]+calc(a[f[0]]<=a[f.back()]?a[f.back()]-a[f[0]]:a[f.back()]+l-a[f[0]]); if(f.size()==1) len=calc(l); vector<ll> xs1,xs2; for(int i=0;i<sz;i++){ for(auto&p:my[f[i]]){ xs1.pb(d[i]-p); xs2.pb(d[i]-p-divb(d[i]-p,len)); } for(auto&p:qs[f[i]]){ xs1.pb(-(p.fi-d[i])); xs2.pb(len-(p.fi-d[i]-divb(p.fi-d[i],len))); } } sort(xs1.begin(),xs1.end()); xs1.erase(unique(xs1.begin(),xs1.end()),xs1.end()); sort(xs2.begin(),xs2.end()); xs2.erase(unique(xs2.begin(),xs2.end()),xs2.end()); int sz1=(int)xs1.size(),sz2=(int)xs2.size(); for(int i=0;i<sz;i++){ for(auto&p:my[f[i]]){ int idx1=(int)(lower_bound(xs1.begin(),xs1.end(),d[i]-p)-xs1.begin()); int idx2=(int)(lower_bound(xs2.begin(),xs2.end(),d[i]-p-divb(d[i]-p,len))-xs2.begin()); modifyx(idx1,idx2,divb(d[i]-p,len)); } for(auto&p:qs[f[i]]){ int idx1=(int)(lower_bound(xs1.begin(),xs1.end(),-(p.fi-d[i]))-xs1.begin()); int idx2=(int)(lower_bound(xs2.begin(),xs2.end(),len-(p.fi-d[i]-divb(p.fi-d[i],len)))-xs2.begin()); pair<ll,int> tmp=queryx(idx1,sz1-1,0,sz2-1); ll s=tmp.se*(divb(p.fi-d[i],len)/len)+tmp.se+tmp.fi/len; ans[p.se]+=s+queryx(idx1,sz1-1,idx2,sz2-1).se; } } while(tsz){ ls[tsz]=rs[tsz]=sum[tsz]=cnt[tsz]=0; tsz--; } for(int i=0;i<sz;i++) { for(auto&p:my[f[i]]){ int idx1=(int)(lower_bound(xs1.begin(),xs1.end(),d[i]-p)-xs1.begin()); clrx(idx1); } } xs1.clear(); xs2.clear(); for(int i=0;i<sz;i++){ for(auto&p:my[f[i]]){ xs1.pb((d[i]-len)-p); xs2.pb((d[i]-len)-p-divb((d[i]-len)-p,len)); } for(auto&p:qs[f[i]]){ xs1.pb(-(p.fi-d[i])); xs2.pb(len-(p.fi-d[i]-divb(p.fi-d[i],len))); } } sort(xs1.begin(),xs1.end()); xs1.erase(unique(xs1.begin(),xs1.end()),xs1.end()); sort(xs2.begin(),xs2.end()); xs2.erase(unique(xs2.begin(),xs2.end()),xs2.end()); sz1=(int)xs1.size(),sz2=(int)xs2.size(); for(int i=sz-1;i>=0;i--){ for(auto&p:qs[f[i]]){ int idx1=(int)(lower_bound(xs1.begin(),xs1.end(),-(p.fi-d[i]))-xs1.begin()); int idx2=(int)(lower_bound(xs2.begin(),xs2.end(),len-(p.fi-d[i]-divb(p.fi-d[i],len)))-xs2.begin()); pair<ll,int> tmp=queryx(idx1,sz1-1,0,sz2-1); ll s=tmp.se*(divb(p.fi-d[i],len)/len)+tmp.se+tmp.fi/len; ans[p.se]+=s+queryx(idx1,sz1-1,idx2,sz2-1).se; } for(auto&p:my[f[i]]){ int idx1=(int)(lower_bound(xs1.begin(),xs1.end(),(d[i]-len)-p)-xs1.begin()); int idx2=(int)(lower_bound(xs2.begin(),xs2.end(),(d[i]-len)-p-divb((d[i]-len)-p,len))-xs2.begin()); modifyx(idx1,idx2,divb((d[i]-len)-p,len)); } } while(tsz){ ls[tsz]=rs[tsz]=sum[tsz]=cnt[tsz]=0; tsz--; } for(int i=0;i<sz;i++) { for(auto&p:my[f[i]]){ int idx1=(int)(lower_bound(xs1.begin(),xs1.end(),(d[i]-len)-p)-xs1.begin()); clrx(idx1); } } } for(int i=1;i<=q;i++) printf("%lld\n",ans[i]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...