oj.uz

Submission #942288

# Submission time Handle Problem Language Result Execution time Memory
942288 2024-03-10T12:01:34 Z MilosMilutinovic Harvest (JOI20_harvest) C++14
25 / 100
 2803 ms 252384 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[30000005],ls[30000005],rs[30000005],root[400005];
ll d[200005],sum[30000005];
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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 29276 KB Output is correct
2 Correct 16 ms 25180 KB Output is correct
3 Correct 26 ms 33628 KB Output is correct
4 Correct 15 ms 37916 KB Output is correct
5 Correct 14 ms 38432 KB Output is correct
6 Correct 14 ms 38428 KB Output is correct
7 Correct 14 ms 38396 KB Output is correct
8 Correct 15 ms 37464 KB Output is correct
9 Correct 15 ms 37468 KB Output is correct
10 Correct 14 ms 38100 KB Output is correct
11 Correct 13 ms 37844 KB Output is correct
12 Correct 26 ms 29020 KB Output is correct
13 Correct 27 ms 33624 KB Output is correct
14 Correct 24 ms 29532 KB Output is correct
15 Correct 14 ms 38136 KB Output is correct
16 Correct 17 ms 38428 KB Output is correct
17 Correct 14 ms 38172 KB Output is correct
18 Correct 15 ms 38176 KB Output is correct
19 Correct 16 ms 38168 KB Output is correct
20 Correct 16 ms 38168 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1330 ms 43068 KB Output is correct
2 Correct 172 ms 47176 KB Output is correct
3 Correct 171 ms 35308 KB Output is correct
4 Correct 1508 ms 48884 KB Output is correct
5 Correct 174 ms 85944 KB Output is correct
6 Correct 144 ms 87632 KB Output is correct
7 Correct 105 ms 45088 KB Output is correct
8 Correct 115 ms 52920 KB Output is correct
9 Correct 1555 ms 47560 KB Output is correct
10 Correct 1380 ms 49228 KB Output is correct
11 Correct 1627 ms 47468 KB Output is correct
12 Correct 1623 ms 47560 KB Output is correct
13 Correct 1579 ms 47608 KB Output is correct
14 Correct 1460 ms 49732 KB Output is correct
15 Correct 1157 ms 44304 KB Output is correct
16 Correct 147 ms 71888 KB Output is correct
17 Correct 136 ms 72740 KB Output is correct
18 Correct 96 ms 55216 KB Output is correct
19 Correct 100 ms 55676 KB Output is correct
20 Correct 118 ms 47952 KB Output is correct

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 29276 KB Output is correct
2 Correct 16 ms 25180 KB Output is correct
3 Correct 26 ms 33628 KB Output is correct
4 Correct 15 ms 37916 KB Output is correct
5 Correct 14 ms 38432 KB Output is correct
6 Correct 14 ms 38428 KB Output is correct
7 Correct 14 ms 38396 KB Output is correct
8 Correct 15 ms 37464 KB Output is correct
9 Correct 15 ms 37468 KB Output is correct
10 Correct 14 ms 38100 KB Output is correct
11 Correct 13 ms 37844 KB Output is correct
12 Correct 26 ms 29020 KB Output is correct
13 Correct 27 ms 33624 KB Output is correct
14 Correct 24 ms 29532 KB Output is correct
15 Correct 14 ms 38136 KB Output is correct
16 Correct 17 ms 38428 KB Output is correct
17 Correct 14 ms 38172 KB Output is correct
18 Correct 15 ms 38176 KB Output is correct
19 Correct 16 ms 38168 KB Output is correct
20 Correct 16 ms 38168 KB Output is correct
21 Correct 1330 ms 43068 KB Output is correct
22 Correct 172 ms 47176 KB Output is correct
23 Correct 171 ms 35308 KB Output is correct
24 Correct 1508 ms 48884 KB Output is correct
25 Correct 174 ms 85944 KB Output is correct
26 Correct 144 ms 87632 KB Output is correct
27 Correct 105 ms 45088 KB Output is correct
28 Correct 115 ms 52920 KB Output is correct
29 Correct 1555 ms 47560 KB Output is correct
30 Correct 1380 ms 49228 KB Output is correct
31 Correct 1627 ms 47468 KB Output is correct
32 Correct 1623 ms 47560 KB Output is correct
33 Correct 1579 ms 47608 KB Output is correct
34 Correct 1460 ms 49732 KB Output is correct
35 Correct 1157 ms 44304 KB Output is correct
36 Correct 147 ms 71888 KB Output is correct
37 Correct 136 ms 72740 KB Output is correct
38 Correct 96 ms 55216 KB Output is correct
39 Correct 100 ms 55676 KB Output is correct
40 Correct 118 ms 47952 KB Output is correct
41 Correct 684 ms 214992 KB Output is correct
42 Correct 833 ms 41004 KB Output is correct
43 Correct 1380 ms 46932 KB Output is correct
44 Correct 2635 ms 239764 KB Output is correct
45 Correct 577 ms 251604 KB Output is correct
46 Correct 606 ms 250852 KB Output is correct
47 Correct 576 ms 252384 KB Output is correct
48 Correct 579 ms 248004 KB Output is correct
49 Correct 540 ms 249960 KB Output is correct
50 Correct 515 ms 200156 KB Output is correct
51 Correct 527 ms 216376 KB Output is correct
52 Correct 2799 ms 237016 KB Output is correct
53 Correct 1940 ms 201772 KB Output is correct
54 Correct 2803 ms 238664 KB Output is correct
55 Correct 2019 ms 245252 KB Output is correct
56 Incorrect 674 ms 241088 KB Output isn't correct
57 Halted 0 ms 0 KB -