oj.uz

Submission #282082

# Submission time Handle Problem Language Result Execution time Memory
282082 2020-08-24T00:23:09 Z amoo_safar Harvest (JOI20_harvest) C++17
5 / 100
 285 ms 56628 KB 
// 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());
	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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14848 KB Output is correct
2 Correct 16 ms 15360 KB Output is correct
3 Correct 14 ms 15328 KB Output is correct
4 Correct 15 ms 15488 KB Output is correct
5 Correct 15 ms 15488 KB Output is correct
6 Correct 14 ms 15488 KB Output is correct
7 Correct 15 ms 15616 KB Output is correct
8 Correct 14 ms 15360 KB Output is correct
9 Correct 14 ms 15360 KB Output is correct
10 Correct 14 ms 15360 KB Output is correct
11 Correct 14 ms 15360 KB Output is correct
12 Correct 15 ms 15616 KB Output is correct
13 Correct 16 ms 15616 KB Output is correct
14 Correct 16 ms 15488 KB Output is correct
15 Correct 15 ms 15488 KB Output is correct
16 Correct 15 ms 15488 KB Output is correct
17 Correct 15 ms 15488 KB Output is correct
18 Correct 14 ms 15392 KB Output is correct
19 Correct 14 ms 15392 KB Output is correct
20 Correct 14 ms 15488 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 24728 KB Output is correct
2 Incorrect 285 ms 56628 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14848 KB Output is correct
2 Correct 16 ms 15360 KB Output is correct
3 Correct 14 ms 15328 KB Output is correct
4 Correct 15 ms 15488 KB Output is correct
5 Correct 15 ms 15488 KB Output is correct
6 Correct 14 ms 15488 KB Output is correct
7 Correct 15 ms 15616 KB Output is correct
8 Correct 14 ms 15360 KB Output is correct
9 Correct 14 ms 15360 KB Output is correct
10 Correct 14 ms 15360 KB Output is correct
11 Correct 14 ms 15360 KB Output is correct
12 Correct 15 ms 15616 KB Output is correct
13 Correct 16 ms 15616 KB Output is correct
14 Correct 16 ms 15488 KB Output is correct
15 Correct 15 ms 15488 KB Output is correct
16 Correct 15 ms 15488 KB Output is correct
17 Correct 15 ms 15488 KB Output is correct
18 Correct 14 ms 15392 KB Output is correct
19 Correct 14 ms 15392 KB Output is correct
20 Correct 14 ms 15488 KB Output is correct
21 Correct 137 ms 24728 KB Output is correct
22 Incorrect 285 ms 56628 KB Output isn't correct
23 Halted 0 ms 0 KB -