Submission #1068594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068594		AdamGS	Harvest (JOI20_harvest)	C++17	0 / 100	122 ms	74104 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=4e5+7;
vector<ll>S[LIM];
vector<pair<ll,ll>>V[LIM], pyt[LIM], pyt2[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) if(n>1) {
		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;
	}
	if(n==1) {
		kraw[0]=(C+L-1)/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]) {
			pyt2[korzen[i]].pb({j.st-d, j.nd});
		}
	}
	rep(i, n) if(korzen[i]==i && S[i].size()) {
		ll m=suma[i];
		vector<ll>K;
		for(auto j : S[i]) K.pb(j%m);
		sort(all(K));
		sort(all(S[i]));
		sort(all(pyt2[i]));
		l=0;
		ll ilek=0, sumk=0;
		N=1;
		while(N<K.size()) N*=2;
		rep(j, 2*N) tr[j]=0;
		for(auto j : pyt2[i]) {
			while(l<S[i].size() && S[i][l]<=j.st) {
				++ilek;
				sumk+=S[i][l]/m;
				ll po=0, ko=K.size()-1;
				while(po<ko) {
					ll sr=(po+ko+1)/2;
					if(K[sr]>S[i][l]%m) ko=sr-1; else po=sr;
				}
				upd(po, 1);
				++l;
			}
			ll po=0, ko=K.size()-1;
			while(po<ko) {
				ll sr=(po+ko+1)/2;
				if(K[sr]>j.st%m) ko=sr-1; else po=sr;
			}
			if(K[po]<=j.st%m) wynik[j.nd]+=cnt(0, po);
			wynik[j.nd]+=ilek*(j.st/m);
			wynik[j.nd]-=sumk;
		}
	}
	rep(i, q) cout << wynik[i] << '\n';
}

Compilation message (stderr)

harvest.cpp: In function 'int main()':
harvest.cpp:130:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |   while(N<K.size()) N*=2;
      |         ~^~~~~~~~~
harvest.cpp:133:11: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |    while(l<S[i].size() && S[i][l]<=j.st) {
      |          ~^~~~~~~~~~~~

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