제출 #941883

#제출 시각아이디문제언어결과실행 시간메모리
941883MilosMilutinovic수확 (JOI20_harvest)C++14
5 / 100
5041 ms24312 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; int a[200005],b[200005],prv[200005],deg[200005],rt[200005],fenw[200005],dfn[200005],dfo[200005]; ll d[200005]; 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;} 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<200005;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; } 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(); vector<int> tmp=f; for(int i=0;i<sz;i++){ f.clear(); int ver=tmp[i]; for(int j=0;j<sz;j++) f.pb(ver),ver=prv[ver]; d[0]=0; for(int j=1;j<sz;j++){ ll w=calc(a[f[j]]<=a[f[j-1]]?a[f[j-1]]-a[f[j]]:a[f[j-1]]+l-a[f[j]]); d[j]=d[j-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); for(int j=0;j<sz;j++){ for(auto&p:my[f[0]]){ for(auto&pp:qs[f[j]]){ ans[pp.se]+=max(0ll,pp.fi-d[j]-p+len)/len; } } } } } 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...