oj.uz

Submission #941929

# Submission time Handle Problem Language Result Execution time Memory
941929 2024-03-09T18:09:33 Z MilosMilutinovic Harvest (JOI20_harvest) C++14
5 / 100
 5000 ms 24264 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;
int a[200005],b[200005],prv[200005],deg[200005],rt[200005],fenw[200005],dfn[200005],dfo[200005];
ll d[200005];
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;}

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<200005;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;
}

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);
		for(int i=0;i<sz;i++){
			for(int j=0;j<sz;j++){
				for(auto&p:my[f[i]]){
					for(auto&pp:qs[f[j]]){
						ans[pp.se]+=max(0ll,pp.fi-(i<=j?d[j]-d[i]:d[j]+len-d[i])-p+len)/len;
					}
				}
			}
		}
	}
	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 5 ms 21084 KB Output is correct
2 Correct 5 ms 21084 KB Output is correct
3 Correct 85 ms 21204 KB Output is correct
4 Correct 8 ms 23640 KB Output is correct
5 Correct 8 ms 24096 KB Output is correct
6 Correct 7 ms 24088 KB Output is correct
7 Correct 7 ms 24060 KB Output is correct
8 Correct 6 ms 23280 KB Output is correct
9 Correct 6 ms 23132 KB Output is correct
10 Correct 6 ms 23492 KB Output is correct
11 Correct 6 ms 23512 KB Output is correct
12 Correct 58 ms 21080 KB Output is correct
13 Correct 64 ms 21236 KB Output is correct
14 Correct 39 ms 21212 KB Output is correct
15 Correct 7 ms 23804 KB Output is correct
16 Correct 7 ms 23808 KB Output is correct
17 Correct 7 ms 23836 KB Output is correct
18 Correct 8 ms 23644 KB Output is correct
19 Correct 7 ms 23836 KB Output is correct
20 Correct 6 ms 23768 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5005 ms 24264 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Correct 5 ms 21084 KB Output is correct
3 Correct 85 ms 21204 KB Output is correct
4 Correct 8 ms 23640 KB Output is correct
5 Correct 8 ms 24096 KB Output is correct
6 Correct 7 ms 24088 KB Output is correct
7 Correct 7 ms 24060 KB Output is correct
8 Correct 6 ms 23280 KB Output is correct
9 Correct 6 ms 23132 KB Output is correct
10 Correct 6 ms 23492 KB Output is correct
11 Correct 6 ms 23512 KB Output is correct
12 Correct 58 ms 21080 KB Output is correct
13 Correct 64 ms 21236 KB Output is correct
14 Correct 39 ms 21212 KB Output is correct
15 Correct 7 ms 23804 KB Output is correct
16 Correct 7 ms 23808 KB Output is correct
17 Correct 7 ms 23836 KB Output is correct
18 Correct 8 ms 23644 KB Output is correct
19 Correct 7 ms 23836 KB Output is correct
20 Correct 6 ms 23768 KB Output is correct
21 Execution timed out 5005 ms 24264 KB Time limit exceeded
22 Halted 0 ms 0 KB -