oj.uz

Submission #715804

# Submission time Handle Problem Language Result Execution time Memory
715804 2023-03-28T01:56:40 Z pavement Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 101800 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define g4(a) get<4>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
using iiiii = tuple<int, int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, M, L, C, Q, A[200005], B[200005], off[200005], lnk[200005], sz[200005], ans[200005];
bool on_cycle[200005];
ii to[200005];
vector<ii> adj[200005], qu[200005];
ordered_set<ii> T1, S[200005];

int find(int x) {
	if (x == lnk[x]) return x;
	return lnk[x] = find(lnk[x]);
}

void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	if (sz[b] > sz[a]) swap(a, b);
	sz[a] += sz[b];
	lnk[b] = a;
}

void solve_tree(int n) {
	for (auto [u, w] : adj[n]) {
		solve_tree(u);
		off[u] += w;
		if (S[u].size() > S[n].size()) {
			swap(S[n], S[u]);
			swap(off[n], off[u]);
		}
		for (auto v : S[u]) {
			S[n].insert(mp(v.first + off[u] - off[n], v.second));
		}
	}
	for (auto [t, idx] : qu[n]) {
		ans[idx] = S[n].order_of_key(mp(t - off[n], LLONG_MAX));
	}
}

vector<vector<iii> > adds, qus;

void cdq(int l, int r) {
	if (l == r) return;
	int m = (l + r) / 2;
	vector<iii> sort_by;
	for (int i = l; i <= m; i++) {
		for (auto [a, q, r] : adds[i]) {
			sort_by.eb(a, q, r);
		}
	}
	for (int i = m + 1; i <= r; i++) {
		for (auto [b, r, idx] : qus[i]) {
			sort_by.eb(b, r, -idx);
		}
	}
	int pf = 0, _ = 0;
	ordered_set<ii> O;
	sort(sort_by.begin(), sort_by.end(), [](const auto &lhs, const auto &rhs) {
		if (g0(lhs) != g0(rhs)) return lhs < rhs;
		else if ((g2(lhs) >= 0) != (g2(rhs) >= 0)) return g2(lhs) > g2(rhs);
		else return lhs < rhs;
	});
	for (auto [a, b, c] : sort_by) {
		if (c < 0) {
			ans[-c] -= pf;
			ans[-c] -= O.order_of_key(mp(b, (int)LLONG_MAX));
		} else {
			pf += b;
			O.insert(mp(c, _++));
		}
	}
	cdq(l, m);
	cdq(m + 1, r);
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M >> L >> C;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		lnk[i] = i;
		sz[i] = 1;
	}
	for (int i = 1; i <= N; i++) {
		int pos = ((A[i] - C) % L + L) % L;
		auto it = upper_bound(A + 1, A + 1 + N, pos);
		if (it == A + 1) {
			to[i] = mp(N, pos + L - A[N] + C);
		} else {
			--it;
			to[i] = mp(it - A, pos - *it + C);
		}
		unite(i, to[i].first);
		adj[to[i].first].eb(i, to[i].second);
	}
	for (int i = 1; i <= M; i++) {
		cin >> B[i];
		auto it = lower_bound(A + 1, A + 1 + N, B[i]);
		if (it == A + 1) {
			S[N].insert(mp(B[i] + L - A[N], i));
		} else {
			--it;
			S[it - A].insert(mp(B[i] - *it, i));
		}
	}
	cin >> Q;
	for (int i = 1, V, T; i <= Q; i++) {
		cin >> V >> T;
		qu[V].eb(T, i);
	}
	// handle nodes not on cycle
	for (int i = 1; i <= N; i++) {
		if (i == find(i)) {
			int tort = i, hare = i;
			do {
				hare = to[to[hare].first].first;
				tort = to[tort].first;
			} while (tort != hare);
			do {
				on_cycle[tort] = 1;
				tort = to[tort].first;
			} while (tort != hare);
		}
	}
	for (int i = 1; i <= N; i++) {
		if (on_cycle[i]) {
			for (auto [u, w] : adj[i]) if (!on_cycle[u]) {
				solve_tree(u);
				off[u] += w;
				if (S[u].size() > S[i].size()) {
					swap(S[i], S[u]);
					swap(off[i], off[u]);
				}
				for (auto v : S[u]) {
					S[i].insert(mp(v.first + off[u] - off[i], v.second));
				}
			}
		}
	}
	// handle nodes on cycle
	for (int i = 1; i <= N; i++) {
		if (i == find(i)) {
			int tort = i, hare = i;
			do {
				hare = to[to[hare].first].first;
				tort = to[tort].first;
			} while (tort != hare);
			vector<int> ord;
			int len = 0;
			do {
				ord.pb(tort);
				len += to[tort].second;
				tort = to[tort].first;
			} while (tort != hare);
			int P = 0;
			T1.clear();
			adds.clear();
			qus.clear();
			qus.pb(vector<iii>());
			for (auto x : ord) {
				vector<iii> cur_add, cur_qu;
				for (auto [v, idx] : S[x]) {
					int a = v + off[x] - P;
					int q2 = a / len, r2 = a % len;
					if (r2 < 0) {
						r2 += len;
						q2--;
					}
					cur_add.eb(a, q2, len - r2);
					T1.insert(mp(a, idx));
				}
				adds.pb(cur_add);
				for (auto [t, idx] : qu[x]) {
					int b = t - P + len;
					int q1 = b / len, r1 = b % len;
					if (r1 < 0) {
						r1 += len;
						q1--;
					}
					cur_qu.eb(b, len - r1 - 1, idx);
					ans[idx] += q1 * T1.order_of_key(mp(b, LLONG_MAX));
				}
				qus.pb(cur_qu);
				P += to[x].second;
			}
			adds.pb(vector<iii>());
			assert(adds.size() == qus.size());
			if (!adds.empty()) cdq(0, (int)adds.size() - 1);
			reverse(ord.begin(), ord.end());
			P = 0;
			T1.clear();
			adds.clear();
			qus.clear();
			for (auto x : ord) {
				vector<iii> cur_add, cur_qu;
				P += to[x].second;
				for (auto [v, idx] : S[x]) {
					int a = v + off[x] + P;
					int q2 = a / len, r2 = a % len;
					if (r2 < 0) {
						r2 += len;
						q2--;
					}
					cur_add.eb(a, q2, len - r2);
				}
				adds.pb(cur_add);
				for (auto [t, idx] : qu[x]) {
					int b = t + P;
					int q1 = b / len, r1 = b % len;
					if (r1 < 0) {
						r1 += len;
						q1--;
					}
					cur_qu.eb(b, len - r1 - 1, idx);
					ans[idx] += q1 * T1.order_of_key(mp(b, LLONG_MAX));
				}
				for (auto [v, idx] : S[x]) {
					int a = v + off[x] + P;
					int q2 = a / len, r2 = a % len;
					if (r2 < 0) {
						r2 += len;
						q2--;
					}
					T1.insert(mp(a, idx));
				}
				qus.pb(cur_qu);
			}
			assert(adds.size() == qus.size());
			if (!adds.empty()) cdq(0, (int)adds.size() - 1);
		}
	}
	for (int i = 1; i <= Q; i++) {
		cout << ans[i] << '\n';
	}
}

Compilation message

harvest.cpp:101:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  101 | main() {
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 28884 KB Output is correct
2 Correct 23 ms 29096 KB Output is correct
3 Correct 34 ms 29668 KB Output is correct
4 Correct 37 ms 30308 KB Output is correct
5 Correct 193 ms 30376 KB Output is correct
6 Correct 203 ms 30364 KB Output is correct
7 Correct 193 ms 30412 KB Output is correct
8 Correct 27 ms 29668 KB Output is correct
9 Correct 26 ms 29740 KB Output is correct
10 Correct 27 ms 29656 KB Output is correct
11 Correct 28 ms 29724 KB Output is correct
12 Correct 35 ms 29964 KB Output is correct
13 Correct 34 ms 29912 KB Output is correct
14 Correct 30 ms 29552 KB Output is correct
15 Correct 109 ms 30120 KB Output is correct
16 Correct 113 ms 30148 KB Output is correct
17 Correct 108 ms 30280 KB Output is correct
18 Correct 118 ms 30016 KB Output is correct
19 Correct 129 ms 30124 KB Output is correct
20 Correct 115 ms 29996 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 49364 KB Output is correct
2 Correct 321 ms 53616 KB Output is correct
3 Correct 237 ms 57204 KB Output is correct
4 Correct 242 ms 70576 KB Output is correct
5 Execution timed out 5060 ms 101800 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 28884 KB Output is correct
2 Correct 23 ms 29096 KB Output is correct
3 Correct 34 ms 29668 KB Output is correct
4 Correct 37 ms 30308 KB Output is correct
5 Correct 193 ms 30376 KB Output is correct
6 Correct 203 ms 30364 KB Output is correct
7 Correct 193 ms 30412 KB Output is correct
8 Correct 27 ms 29668 KB Output is correct
9 Correct 26 ms 29740 KB Output is correct
10 Correct 27 ms 29656 KB Output is correct
11 Correct 28 ms 29724 KB Output is correct
12 Correct 35 ms 29964 KB Output is correct
13 Correct 34 ms 29912 KB Output is correct
14 Correct 30 ms 29552 KB Output is correct
15 Correct 109 ms 30120 KB Output is correct
16 Correct 113 ms 30148 KB Output is correct
17 Correct 108 ms 30280 KB Output is correct
18 Correct 118 ms 30016 KB Output is correct
19 Correct 129 ms 30124 KB Output is correct
20 Correct 115 ms 29996 KB Output is correct
21 Correct 165 ms 49364 KB Output is correct
22 Correct 321 ms 53616 KB Output is correct
23 Correct 237 ms 57204 KB Output is correct
24 Correct 242 ms 70576 KB Output is correct
25 Execution timed out 5060 ms 101800 KB Time limit exceeded
26 Halted 0 ms 0 KB -