oj.uz

답안 #942292

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
942292 2024-03-10T12:04:07 Z MilosMilutinovic 수확 (JOI20_harvest) C++14
25 / 100
 2600 ms 267968 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[600005],fenw[600005],dfn[200005],dfo[200005],cnt[30000005],ls[30000005],rs[30000005],root[600005];
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<600005;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<600005;x|=(x+1)) modifyy(root[x],0,600005,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,600005,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,600005,y1,y2);
		ret.fi-=f.fi;
		ret.se-=f.se;
	}
	return ret;
}
 
void clrx(int x){
	for(;x<600005;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 21 ms 29276 KB Output is correct
2 Correct 16 ms 25404 KB Output is correct
3 Correct 25 ms 33712 KB Output is correct
4 Correct 16 ms 39964 KB Output is correct
5 Correct 15 ms 40472 KB Output is correct
6 Correct 15 ms 40472 KB Output is correct
7 Correct 16 ms 40444 KB Output is correct
8 Correct 16 ms 39772 KB Output is correct
9 Correct 14 ms 39772 KB Output is correct
10 Correct 16 ms 40040 KB Output is correct
11 Correct 14 ms 40148 KB Output is correct
12 Correct 26 ms 29020 KB Output is correct
13 Correct 26 ms 33624 KB Output is correct
14 Correct 26 ms 31672 KB Output is correct
15 Correct 17 ms 40188 KB Output is correct
16 Correct 18 ms 40216 KB Output is correct
17 Correct 15 ms 40216 KB Output is correct
18 Correct 15 ms 40224 KB Output is correct
19 Correct 15 ms 40220 KB Output is correct
20 Correct 18 ms 40216 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1431 ms 43476 KB Output is correct
2 Correct 152 ms 52600 KB Output is correct
3 Correct 187 ms 39392 KB Output is correct
4 Correct 1410 ms 50428 KB Output is correct
5 Correct 147 ms 92864 KB Output is correct
6 Correct 153 ms 92292 KB Output is correct
7 Correct 101 ms 49336 KB Output is correct
8 Correct 132 ms 59444 KB Output is correct
9 Correct 1526 ms 49564 KB Output is correct
10 Correct 1419 ms 52892 KB Output is correct
11 Correct 1510 ms 49444 KB Output is correct
12 Correct 1508 ms 49300 KB Output is correct
13 Correct 1565 ms 49424 KB Output is correct
14 Correct 1346 ms 53080 KB Output is correct
15 Correct 1269 ms 48044 KB Output is correct
16 Correct 142 ms 77584 KB Output is correct
17 Correct 137 ms 77608 KB Output is correct
18 Correct 103 ms 60152 KB Output is correct
19 Correct 106 ms 59744 KB Output is correct
20 Correct 122 ms 52524 KB Output is correct

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 29276 KB Output is correct
2 Correct 16 ms 25404 KB Output is correct
3 Correct 25 ms 33712 KB Output is correct
4 Correct 16 ms 39964 KB Output is correct
5 Correct 15 ms 40472 KB Output is correct
6 Correct 15 ms 40472 KB Output is correct
7 Correct 16 ms 40444 KB Output is correct
8 Correct 16 ms 39772 KB Output is correct
9 Correct 14 ms 39772 KB Output is correct
10 Correct 16 ms 40040 KB Output is correct
11 Correct 14 ms 40148 KB Output is correct
12 Correct 26 ms 29020 KB Output is correct
13 Correct 26 ms 33624 KB Output is correct
14 Correct 26 ms 31672 KB Output is correct
15 Correct 17 ms 40188 KB Output is correct
16 Correct 18 ms 40216 KB Output is correct
17 Correct 15 ms 40216 KB Output is correct
18 Correct 15 ms 40224 KB Output is correct
19 Correct 15 ms 40220 KB Output is correct
20 Correct 18 ms 40216 KB Output is correct
21 Correct 1431 ms 43476 KB Output is correct
22 Correct 152 ms 52600 KB Output is correct
23 Correct 187 ms 39392 KB Output is correct
24 Correct 1410 ms 50428 KB Output is correct
25 Correct 147 ms 92864 KB Output is correct
26 Correct 153 ms 92292 KB Output is correct
27 Correct 101 ms 49336 KB Output is correct
28 Correct 132 ms 59444 KB Output is correct
29 Correct 1526 ms 49564 KB Output is correct
30 Correct 1419 ms 52892 KB Output is correct
31 Correct 1510 ms 49444 KB Output is correct
32 Correct 1508 ms 49300 KB Output is correct
33 Correct 1565 ms 49424 KB Output is correct
34 Correct 1346 ms 53080 KB Output is correct
35 Correct 1269 ms 48044 KB Output is correct
36 Correct 142 ms 77584 KB Output is correct
37 Correct 137 ms 77608 KB Output is correct
38 Correct 103 ms 60152 KB Output is correct
39 Correct 106 ms 59744 KB Output is correct
40 Correct 122 ms 52524 KB Output is correct
41 Correct 757 ms 231620 KB Output is correct
42 Correct 808 ms 44368 KB Output is correct
43 Correct 1490 ms 49388 KB Output is correct
44 Correct 2358 ms 259408 KB Output is correct
45 Correct 574 ms 265604 KB Output is correct
46 Correct 635 ms 267348 KB Output is correct
47 Correct 605 ms 267968 KB Output is correct
48 Correct 584 ms 263692 KB Output is correct
49 Correct 587 ms 265048 KB Output is correct
50 Correct 540 ms 214148 KB Output is correct
51 Correct 565 ms 229288 KB Output is correct
52 Correct 2350 ms 255264 KB Output is correct
53 Correct 1909 ms 220080 KB Output is correct
54 Correct 2600 ms 256820 KB Output is correct
55 Correct 1932 ms 261860 KB Output is correct
56 Incorrect 671 ms 250636 KB Output isn't correct
57 Halted 0 ms 0 KB -