oj.uz

Submission #213256

# Submission time Handle Problem Language Result Execution time Memory
213256 2020-03-25T11:23:03 Z iefnah06 Harvest (JOI20_harvest) C++11
100 / 100
 844 ms 141644 KB 
#ifndef LOCAL
#define DEBUG
#endif
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

namespace __gnu_pbds {
template <typename K, typename V=null_type>
using order_statistic_tree = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;
}
using __gnu_pbds::order_statistic_tree;

using ll = long long;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

	int N, M, L, C; cin >> N >> M >> L >> C;
	auto Xtrans = [&](int x) -> int {
		return L-1-x;
	};
	vector<int> A(N);
	for (int& x : A) {
		cin >> x;
		x = Xtrans(x);
	}
	reverse(A.begin(), A.end());
	vector<int> B(M);
	for (int& x : B) {
		cin >> x;
		x = Xtrans(x);
	}

	vector<int> dest(N);
	vector<int> dist(N);
	for (int i = 0; i < N; i++) {
		int tgt = (A[i] + C) % L;
		auto it = lower_bound(A.begin(), A.end(), tgt);
		if (it == A.end()) {
			dest[i] = 0;
			dist[i] = C + L + A[0] - tgt;
		} else {
			dest[i] = int(distance(A.begin(), it));
			dist[i] = C + *it - tgt;
		}
	}

	vector<bool> vis(N, false);
	vector<bool> isRoot(N, false);
	for (int v = 0; v < N; v++) {
		if (vis[v]) continue;
		int t, h;
		for (t = dest[v], h = dest[dest[v]]; !vis[t] && t != h; t = dest[t], h = dest[dest[h]]) {}

		if (!vis[t]) {
			isRoot[t] = true;
			for (int cur = dest[t]; true; cur = dest[cur]) {
				vis[cur] = true;
				if (cur == t) break;
			}
		}

		for (int cur = v; cur != t; cur = dest[cur]) {
			vis[cur] = true;
		}
	}

	vector<vector<int>> evtsAdd(N);
	for (int i = 0; i < M; i++) {
		auto it = lower_bound(A.begin(), A.end(), B[i]);
		if (it == A.end()) {
			evtsAdd[0].push_back(L + A[0] - B[i]);
		} else {
			evtsAdd[distance(A.begin(), it)].push_back(*it - B[i]);
		}
	}

	int Q; cin >> Q;
	vector<int> V(Q);
	vector<ll> T(Q);
	vector<vector<int>> queriesLoc(N);
	for (int i = 0; i < Q; i++) {
		cin >> V[i] >> T[i];
		V[i]--;
		V[i] = N-1-V[i];
		queriesLoc[V[i]].push_back(i);
	}

	vector<ll> ans(Q);

	vector<vector<int>> ch(N);
	for (int v = 0; v < N; v++) {
		if (!isRoot[v]) {
			ch[dest[v]].push_back(v);
		}
	}
	vector<ll> depth(N);
	for (int v = 0; v < N; v++) {
		if (!isRoot[v]) continue;
		function<void(int, ll)> dfs = [&](int cur, ll curDepth) {
			depth[cur] = curDepth;
			for (int nxt : ch[cur]) {
				dfs(nxt, curDepth + dist[nxt]);
			}
		};
		dfs(v, 0);
	}
	mt19937_64 mt(114514);
	using tree_t = order_statistic_tree<pair<ll, unsigned long long>>;
	vector<tree_t> evtTree(N);
	for (int v = 0; v < N; v++) {
		if (!isRoot[v]) continue;

		function<int(int)> dfs = [&](int cur) -> int {
			int res = cur;
			for (auto t : evtsAdd[cur]) {
				evtTree[res].insert({t + depth[cur], mt()});
			}

			for (int nxt : ch[cur]) {
				int nres = dfs(nxt);
				if (evtTree[res].size() < evtTree[nres].size()) swap(res, nres);
				for (auto t : evtTree[nres]) {
					evtTree[res].insert(t);
				}
				evtTree[nres] = {};
			}

			for (int it : queriesLoc[cur]) {
				ans[it] += evtTree[res].order_of_key({T[it] + depth[cur], -1});
			}

			return res;
		};
		int treeInd = dfs(v);

		ll cycLen = dist[v] + depth[dest[v]];

		vector<pair<ll, int>> toProcess;
		for (auto t : evtTree[treeInd]) {
			toProcess.emplace_back(t.first, -1);
		}
		for (int cur = dest[v]; true; cur = dest[cur]) {
			for (auto it : queriesLoc[cur]) {
				toProcess.emplace_back(T[it] - (cycLen - depth[cur]), it);
			}
			if (cur == v) break;
		}
		sort(toProcess.begin(), toProcess.end());

		tree_t tr;
		ll delta = 0;
		for (auto it : toProcess) {
			ll val = it.first;
			int ind = it.second;
			if (ind == -1) {
				delta -= val / cycLen;
				tr.insert({val % cycLen, mt()});
			} else {
				ans[ind] += delta + ll(tr.size()) * (val / cycLen) + tr.order_of_key({val % cycLen, -1});
			}
		}
	}

	for (ll v : ans) {
		cout << v << '\n';
	}

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Output is correct
2 Correct 9 ms 1408 KB Output is correct
3 Correct 10 ms 1536 KB Output is correct
4 Correct 11 ms 1664 KB Output is correct
5 Correct 10 ms 2432 KB Output is correct
6 Correct 10 ms 2432 KB Output is correct
7 Correct 11 ms 2432 KB Output is correct
8 Correct 10 ms 1664 KB Output is correct
9 Correct 10 ms 1664 KB Output is correct
10 Correct 10 ms 1664 KB Output is correct
11 Correct 10 ms 1664 KB Output is correct
12 Correct 11 ms 2432 KB Output is correct
13 Correct 12 ms 2560 KB Output is correct
14 Correct 11 ms 2020 KB Output is correct
15 Correct 11 ms 2048 KB Output is correct
16 Correct 11 ms 2048 KB Output is correct
17 Correct 11 ms 2048 KB Output is correct
18 Correct 10 ms 1924 KB Output is correct
19 Correct 10 ms 2048 KB Output is correct
20 Correct 12 ms 2048 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 13708 KB Output is correct
2 Correct 289 ms 57700 KB Output is correct
3 Correct 254 ms 52856 KB Output is correct
4 Correct 250 ms 53352 KB Output is correct
5 Correct 304 ms 106748 KB Output is correct
6 Correct 299 ms 106676 KB Output is correct
7 Correct 235 ms 53780 KB Output is correct
8 Correct 238 ms 53744 KB Output is correct
9 Correct 360 ms 109800 KB Output is correct
10 Correct 298 ms 106472 KB Output is correct
11 Correct 528 ms 109928 KB Output is correct
12 Correct 468 ms 109816 KB Output is correct
13 Correct 545 ms 109800 KB Output is correct
14 Correct 439 ms 106448 KB Output is correct
15 Correct 387 ms 85680 KB Output is correct
16 Correct 287 ms 83160 KB Output is correct
17 Correct 317 ms 82884 KB Output is correct
18 Correct 151 ms 28540 KB Output is correct
19 Correct 168 ms 28540 KB Output is correct
20 Correct 253 ms 58788 KB Output is correct

Subtask #3
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Output is correct
2 Correct 9 ms 1408 KB Output is correct
3 Correct 10 ms 1536 KB Output is correct
4 Correct 11 ms 1664 KB Output is correct
5 Correct 10 ms 2432 KB Output is correct
6 Correct 10 ms 2432 KB Output is correct
7 Correct 11 ms 2432 KB Output is correct
8 Correct 10 ms 1664 KB Output is correct
9 Correct 10 ms 1664 KB Output is correct
10 Correct 10 ms 1664 KB Output is correct
11 Correct 10 ms 1664 KB Output is correct
12 Correct 11 ms 2432 KB Output is correct
13 Correct 12 ms 2560 KB Output is correct
14 Correct 11 ms 2020 KB Output is correct
15 Correct 11 ms 2048 KB Output is correct
16 Correct 11 ms 2048 KB Output is correct
17 Correct 11 ms 2048 KB Output is correct
18 Correct 10 ms 1924 KB Output is correct
19 Correct 10 ms 2048 KB Output is correct
20 Correct 12 ms 2048 KB Output is correct
21 Correct 160 ms 13708 KB Output is correct
22 Correct 289 ms 57700 KB Output is correct
23 Correct 254 ms 52856 KB Output is correct
24 Correct 250 ms 53352 KB Output is correct
25 Correct 304 ms 106748 KB Output is correct
26 Correct 299 ms 106676 KB Output is correct
27 Correct 235 ms 53780 KB Output is correct
28 Correct 238 ms 53744 KB Output is correct
29 Correct 360 ms 109800 KB Output is correct
30 Correct 298 ms 106472 KB Output is correct
31 Correct 528 ms 109928 KB Output is correct
32 Correct 468 ms 109816 KB Output is correct
33 Correct 545 ms 109800 KB Output is correct
34 Correct 439 ms 106448 KB Output is correct
35 Correct 387 ms 85680 KB Output is correct
36 Correct 287 ms 83160 KB Output is correct
37 Correct 317 ms 82884 KB Output is correct
38 Correct 151 ms 28540 KB Output is correct
39 Correct 168 ms 28540 KB Output is correct
40 Correct 253 ms 58788 KB Output is correct
41 Correct 736 ms 88180 KB Output is correct
42 Correct 327 ms 68064 KB Output is correct
43 Correct 222 ms 51764 KB Output is correct
44 Correct 650 ms 82000 KB Output is correct
45 Correct 496 ms 137712 KB Output is correct
46 Correct 511 ms 138468 KB Output is correct
47 Correct 514 ms 139108 KB Output is correct
48 Correct 552 ms 136800 KB Output is correct
49 Correct 514 ms 136812 KB Output is correct
50 Correct 526 ms 85972 KB Output is correct
51 Correct 489 ms 85196 KB Output is correct
52 Correct 691 ms 141644 KB Output is correct
53 Correct 766 ms 140744 KB Output is correct
54 Correct 736 ms 141528 KB Output is correct
55 Correct 844 ms 141528 KB Output is correct
56 Correct 546 ms 114144 KB Output is correct
57 Correct 544 ms 115108 KB Output is correct
58 Correct 581 ms 115936 KB Output is correct
59 Correct 568 ms 112792 KB Output is correct
60 Correct 553 ms 112996 KB Output is correct
61 Correct 551 ms 113120 KB Output is correct
62 Correct 688 ms 109852 KB Output is correct
63 Correct 356 ms 57572 KB Output is correct
64 Correct 339 ms 57700 KB Output is correct
65 Correct 376 ms 57956 KB Output is correct
66 Correct 448 ms 57840 KB Output is correct
67 Correct 448 ms 57964 KB Output is correct
68 Correct 479 ms 57264 KB Output is correct
69 Correct 630 ms 92340 KB Output is correct
70 Correct 635 ms 89056 KB Output is correct
71 Correct 618 ms 90344 KB Output is correct
72 Correct 579 ms 90760 KB Output is correct