oj.uz

답안 #942282

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
942282 2024-03-10T11:57:21 Z MilosMilutinovic 수확 (JOI20_harvest) C++14
5 / 100
 1362 ms 36292 KB 
#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[200005];
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<400000;x|=(x+1)) modifyy(root[x],0,400000,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,400000,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,400000,y1,y2);
		ret.fi-=f.fi;
		ret.se-=f.se;
	}
	return ret;
}
 
void clrx(int x){
	for(;x<400000;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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 25180 KB Output is correct
2 Correct 15 ms 21084 KB Output is correct
3 Correct 24 ms 27996 KB Output is correct
4 Correct 15 ms 32404 KB Output is correct
5 Correct 15 ms 32796 KB Output is correct
6 Correct 14 ms 32796 KB Output is correct
7 Correct 14 ms 32764 KB Output is correct
8 Correct 16 ms 32156 KB Output is correct
9 Correct 13 ms 32092 KB Output is correct
10 Correct 13 ms 32304 KB Output is correct
11 Correct 13 ms 32368 KB Output is correct
12 Correct 26 ms 25436 KB Output is correct
13 Correct 26 ms 27996 KB Output is correct
14 Correct 25 ms 25804 KB Output is correct
15 Correct 15 ms 32508 KB Output is correct
16 Correct 14 ms 32540 KB Output is correct
17 Correct 14 ms 32512 KB Output is correct
18 Correct 14 ms 32796 KB Output is correct
19 Correct 14 ms 32536 KB Output is correct
20 Correct 16 ms 32536 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1362 ms 36292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 25180 KB Output is correct
2 Correct 15 ms 21084 KB Output is correct
3 Correct 24 ms 27996 KB Output is correct
4 Correct 15 ms 32404 KB Output is correct
5 Correct 15 ms 32796 KB Output is correct
6 Correct 14 ms 32796 KB Output is correct
7 Correct 14 ms 32764 KB Output is correct
8 Correct 16 ms 32156 KB Output is correct
9 Correct 13 ms 32092 KB Output is correct
10 Correct 13 ms 32304 KB Output is correct
11 Correct 13 ms 32368 KB Output is correct
12 Correct 26 ms 25436 KB Output is correct
13 Correct 26 ms 27996 KB Output is correct
14 Correct 25 ms 25804 KB Output is correct
15 Correct 15 ms 32508 KB Output is correct
16 Correct 14 ms 32540 KB Output is correct
17 Correct 14 ms 32512 KB Output is correct
18 Correct 14 ms 32796 KB Output is correct
19 Correct 14 ms 32536 KB Output is correct
20 Correct 16 ms 32536 KB Output is correct
21 Incorrect 1362 ms 36292 KB Output isn't correct
22 Halted 0 ms 0 KB -