Submission #282083

#	Time	Username	Problem	Language	Result	Execution time	Memory
282083		amoo_safar	Harvest (JOI20_harvest)	C++17	100 / 100	502 ms	86988 KiB

harvest

// That's How much we have in common
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
#define int ll

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const int inf = 2'000'000'000;
const ll Log = 30;

int n, m, C, L, Q;
int A[N], B[N];
int nx[N], w[N], fs[N], df[N];
int V[N], T[N], ans[N];

vector<int> GI[N], TR[N], QR[N];
int slv[N];
int mk[N], incyc[N], st[N], fn[N], Tm = 1;

ll dep[N], deptr[N], al[N];
vector<int> vis, cyc;
void DFS(int u, ll d = 0){
	slv[u] = 1;
	st[u] = Tm ++;
	dep[u] = d;
	vis.pb(u);
	for(auto adj : GI[u]){
		if(!slv[adj])
			DFS(adj, d + w[adj]);
	}
	fn[u] = Tm;
}

int fen[N];
void Add(int idx, int d){
	for(; idx < N; idx += (idx & -idx))
		fen[idx] += d;
}
int Get(int idx){
	int res = 0;
	for(; idx; idx -= (idx & -idx))
		res += fen[idx];
	return res;
}

vector<int> UN;

int ID(ll x){
	return upper_bound(all(UN), x) - UN.begin();
}

void Solve(int rt){
	//debug(rt);
	vis.clear();
	DFS(rt, 0);

	cyc.clear();
	int nw = rt;
	do {
		cyc.pb(nw);
		incyc[nw] = 1;
		nw = nx[nw];
	} while(nw != rt);
	ll CL = 0;
	for(auto x : cyc) CL += w[x];
	for(int i = 1; i < (int) cyc.size(); i++) al[cyc[i]] = al[cyc[i - 1]] + w[cyc[i - 1]];
	//debug(CL);

	vector<pll> E;
	for(auto nd : vis){
		for(auto ap : TR[nd]){
			deptr[ap] = dep[nd] + df[ap];
			E.pb({deptr[ap], -st[nd]});
		}
		if(nd != rt){
			for(auto qr : QR[nd])
				E.pb({T[qr] + dep[nd], qr});
		}
	}
	sort(all(E));
	for(auto ev : E){
		if(ev.S < 0){
			Add(-ev.S, 1);
		} else {
			ans[ev.S] += Get(fn[V[ev.S]] - 1) - Get(st[V[ev.S]] - 1);
		}
	}
	// Clear
	for(auto ev : E)
		if(ev.S < 0)
			Add(-ev.S, -1);
	/////////////////////////////
	E.clear();
	UN.clear();
	for(auto nd : vis){
		for(auto ap : TR[nd]){
			deptr[ap] = dep[nd] + df[ap];
			E.pb({deptr[ap], -1});
			UN.pb(deptr[ap] % CL);
		}
		if(incyc[nd]){
			for(auto qr : QR[nd])
				E.pb({T[qr] - al[nd], qr});
		}
	}
	sort(all(UN)); UN.resize(unique(all(UN)) - UN.begin()); //UN.pb(CL);
	assert(UN.size() < N);

	sort(all(E));
	ll Sum = 0, On;
	for(auto ev : E){
		if(ev.S < 0){
			Sum += ev.F / CL;
			Add(ID(ev.F % CL), 1);
		} else {
			On = Get(UN.size());
			if(On == 0) continue;
			ans[ev.S] += (On * (ev.F / CL)) - Sum;
			ans[ev.S] += Get(ID(ev.F % CL));
		}
	}
	for(auto ev : E){
		if(ev.S < 0){
			Add(ID(ev.F % CL), -1);
		}
	}

}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> L >> C;
	for(int i = 0; i < n; i++) cin >> A[i];
	A[n] = inf;
	for(int i = 0; i < m; i++) cin >> B[i];
	cin >> Q;
	for(int i = 0; i < Q; i++){ cin >> V[i] >> T[i]; V[i] --; }
	for(int i = 0; i < Q; i++) QR[V[i]].pb(i);

	for(int i = 0; i < n; i++){
		int wh = (((A[i] - C) % L) + L) % L;
		if(wh < A[0]) nx[i] = n - 1;
		else 
			nx[i] = (upper_bound(A, A + n, wh) - A) - 1;
		w[i] = C + ((wh - A[nx[i]] + L) % L);
		GI[nx[i]].pb(i);
	}
	for(int i = 0; i < m; i++){
		int wh = B[i];
		if(wh < A[0]) fs[i] = n - 1;
		else 
			fs[i] = (upper_bound(A, A + n, wh) - A) - 1;
		df[i] = (wh - A[fs[i]] + L) % L;
		TR[fs[i]].pb(i);
	}
	/*
	cerr << "! ";
	for(int i = 0; i < m; i++) cerr << df[i] << ' ';
	cerr << '\n';
	*/
	for(int i = 0; i < n; i++){
		if(slv[i]) continue;
		int nw = i;
		mk[nw] = 1;
		int src = -1;
		while(src == -1){
			nw = nx[nw];
			if(mk[nw]) src = nw;
			mk[nw] = 1;
		}
		Solve(src);
	}
	for(int i = 0; i < Q; i++) cout << ans[i] << '\n';
	return 0;
}

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