oj.uz

Submission #942285

# Submission time Handle Problem Language Result Execution time Memory
942285 2024-03-10T12:00:27 Z MilosMilutinovic Harvest (JOI20_harvest) C++14
25 / 100
 2889 ms 264216 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[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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 29272 KB Output is correct
2 Correct 18 ms 25180 KB Output is correct
3 Correct 25 ms 31580 KB Output is correct
4 Correct 16 ms 33820 KB Output is correct
5 Correct 14 ms 34328 KB Output is correct
6 Correct 14 ms 36380 KB Output is correct
7 Correct 15 ms 36600 KB Output is correct
8 Correct 14 ms 35688 KB Output is correct
9 Correct 13 ms 33624 KB Output is correct
10 Correct 13 ms 35904 KB Output is correct
11 Correct 16 ms 35880 KB Output is correct
12 Correct 27 ms 27484 KB Output is correct
13 Correct 26 ms 31580 KB Output is correct
14 Correct 26 ms 29556 KB Output is correct
15 Correct 15 ms 34040 KB Output is correct
16 Correct 18 ms 36120 KB Output is correct
17 Correct 14 ms 36124 KB Output is correct
18 Correct 15 ms 36120 KB Output is correct
19 Correct 14 ms 36120 KB Output is correct
20 Correct 15 ms 36124 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1356 ms 39460 KB Output is correct
2 Correct 139 ms 52296 KB Output is correct
3 Correct 188 ms 42840 KB Output is correct
4 Correct 1493 ms 54196 KB Output is correct
5 Correct 144 ms 92816 KB Output is correct
6 Correct 149 ms 91200 KB Output is correct
7 Correct 97 ms 47844 KB Output is correct
8 Correct 117 ms 57012 KB Output is correct
9 Correct 1562 ms 54004 KB Output is correct
10 Correct 1387 ms 57784 KB Output is correct
11 Correct 1662 ms 53652 KB Output is correct
12 Correct 1601 ms 53684 KB Output is correct
13 Correct 1616 ms 53736 KB Output is correct
14 Correct 1502 ms 57972 KB Output is correct
15 Correct 1094 ms 52048 KB Output is correct
16 Correct 154 ms 77884 KB Output is correct
17 Correct 160 ms 77916 KB Output is correct
18 Correct 129 ms 58116 KB Output is correct
19 Correct 102 ms 59124 KB Output is correct
20 Correct 121 ms 52952 KB Output is correct

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 29272 KB Output is correct
2 Correct 18 ms 25180 KB Output is correct
3 Correct 25 ms 31580 KB Output is correct
4 Correct 16 ms 33820 KB Output is correct
5 Correct 14 ms 34328 KB Output is correct
6 Correct 14 ms 36380 KB Output is correct
7 Correct 15 ms 36600 KB Output is correct
8 Correct 14 ms 35688 KB Output is correct
9 Correct 13 ms 33624 KB Output is correct
10 Correct 13 ms 35904 KB Output is correct
11 Correct 16 ms 35880 KB Output is correct
12 Correct 27 ms 27484 KB Output is correct
13 Correct 26 ms 31580 KB Output is correct
14 Correct 26 ms 29556 KB Output is correct
15 Correct 15 ms 34040 KB Output is correct
16 Correct 18 ms 36120 KB Output is correct
17 Correct 14 ms 36124 KB Output is correct
18 Correct 15 ms 36120 KB Output is correct
19 Correct 14 ms 36120 KB Output is correct
20 Correct 15 ms 36124 KB Output is correct
21 Correct 1356 ms 39460 KB Output is correct
22 Correct 139 ms 52296 KB Output is correct
23 Correct 188 ms 42840 KB Output is correct
24 Correct 1493 ms 54196 KB Output is correct
25 Correct 144 ms 92816 KB Output is correct
26 Correct 149 ms 91200 KB Output is correct
27 Correct 97 ms 47844 KB Output is correct
28 Correct 117 ms 57012 KB Output is correct
29 Correct 1562 ms 54004 KB Output is correct
30 Correct 1387 ms 57784 KB Output is correct
31 Correct 1662 ms 53652 KB Output is correct
32 Correct 1601 ms 53684 KB Output is correct
33 Correct 1616 ms 53736 KB Output is correct
34 Correct 1502 ms 57972 KB Output is correct
35 Correct 1094 ms 52048 KB Output is correct
36 Correct 154 ms 77884 KB Output is correct
37 Correct 160 ms 77916 KB Output is correct
38 Correct 129 ms 58116 KB Output is correct
39 Correct 102 ms 59124 KB Output is correct
40 Correct 121 ms 52952 KB Output is correct
41 Correct 692 ms 224640 KB Output is correct
42 Correct 800 ms 47408 KB Output is correct
43 Correct 1444 ms 51860 KB Output is correct
44 Correct 2705 ms 247136 KB Output is correct
45 Correct 546 ms 263188 KB Output is correct
46 Correct 570 ms 261800 KB Output is correct
47 Correct 572 ms 264216 KB Output is correct
48 Correct 541 ms 257012 KB Output is correct
49 Correct 549 ms 262188 KB Output is correct
50 Correct 489 ms 208316 KB Output is correct
51 Correct 518 ms 221764 KB Output is correct
52 Correct 2835 ms 248664 KB Output is correct
53 Correct 2017 ms 213916 KB Output is correct
54 Correct 2889 ms 248316 KB Output is correct
55 Correct 1983 ms 249624 KB Output is correct
56 Incorrect 650 ms 247088 KB Output isn't correct
57 Halted 0 ms 0 KB -