Submission #1068511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068511		AdamGS	Harvest (JOI20_harvest)	C++17	5 / 100	5071 ms	34260 KiB

harvest

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
vector<ll>S[LIM];
vector<pair<ll,ll>>V[LIM], pyt[LIM];
vector<pair<pair<ll,ll>,ll>>M;
ll A[LIM], B[LIM], n, m, L, C;
pair<ll,ll>T[2*LIM];
ll nxt[LIM], kraw[LIM], odw[LIM], odl[LIM], cykl[LIM], pre[LIM], post[LIM], wynik[LIM], lpre=-1;
ll korzen[LIM], tr[4*LIM], suma[LIM], N=1;
void upd(int v, ll x) {
	v+=N;
	while(v) {
		tr[v]+=x;
		v/=2;
	}
}
ll cnt(int l, int r) {
	if(l>r) return 0;
	l+=N; r+=N;
	ll ans=tr[l];
	if(l!=r) ans+=tr[r];
	while(l/2!=r/2) {
		if(l%2==0) ans+=tr[l+1];
		if(r%2==1) ans+=tr[r-1];
		l/=2; r/=2;
	}
	return ans;
}
void DFS(int x) {
	pre[x]=++lpre;
	for(auto i : V[x]) {
		odl[i.st]=odl[x]+i.nd;
		korzen[i.st]=korzen[x];
		DFS(i.st);
	}
	post[x]=lpre;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> L >> C;
	while(N<n) N*=2;
	rep(i, n) cin >> A[i];
	rep(i, m) cin >> B[i];
	ll l=n-1, d=0;
	for(int i=n-1; i>=0; --i) {
		while(d<C%L) {
			d+=(A[l]-A[(l-1+n)%n]+L)%L;
			l=(l-1+n)%n;
		}
		nxt[i]=l;
		kraw[i]=d;
		if(d<C) kraw[i]+=((C-d+L-1)/L)*L;
		d-=(A[i]-A[(i-1+n)%n]+L)%L;
	}
	rep(i, n) korzen[i]=-1;
	rep(i, n) if(!odw[i]) {
		int p=i;
		while(!odw[p]) {
			odw[p]=i+1;
			p=nxt[p];
		}
		if(odw[p]==i+1) {
			korzen[p]=p;
			int q=p;
			do {
				cykl[q]=1;
				q=nxt[q];
			} while(q!=p);
		}
	}
	rep(i, n) if(korzen[i]!=i) V[nxt[i]].pb({i, kraw[i]});
	rep(i, n) if(korzen[i]==i) DFS(i);
	int q;
	cin >> q;
	rep(i, q) {
		ll v, t;
		cin >> v >> t; --v;
		pyt[v].pb({t, i});
	}
	rep(i, n) T[i]={A[i], i};
	rep(i, m) T[n+i]={B[i], n+i};
	sort(T, T+n+m);
	int lst=0;
	rep(i, n+m) if(T[i].nd<n) lst=T[i].nd;
	rep(i, n+m) {
		if(T[i].nd<n) lst=T[i].nd;
		else {
			S[korzen[lst]].pb(odl[lst]+(T[i].st-A[lst]+L)%L);
			M.pb({{odl[lst]+(T[i].st-A[lst]+L)%L, -1}, lst});
		}
	}
	rep(i, n) if(korzen[i]!=i) {
		for(auto j : pyt[i]) M.pb({{odl[i]+j.st, j.nd}, i});
	}
	sort(all(M));
	for(auto i : M) {
		if(i.st.nd==-1) {
			upd(pre[i.nd], 1);
		} else {
			wynik[i.st.nd]=cnt(pre[i.nd], post[i.nd]);
		}
	}
	rep(i, n) if(cykl[i]) suma[korzen[i]]+=kraw[i];
	rep(i, n) if(cykl[i]) {
		ll m=suma[korzen[i]], d=(m-odl[i])%m;
		for(auto j : pyt[i]) {
			for(auto l : S[korzen[i]]) {
				if(l+d<=j.st) wynik[j.nd]+=(j.st-l-d)/m+1;
			}
		}
	}
	rep(i, q) cout << wynik[i] << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 75