제출 #942285

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
942285		MilosMilutinovic	수확 (JOI20_harvest)	C++14	25 / 100	2889 ms	264216 KiB

harvest

#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]);
}

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 0 / 75