oj.uz

Submission #715807

# Submission time Handle Problem Language Result Execution time Memory
715807 2023-03-28T02:05:20 Z pavement Harvest (JOI20_harvest) C++17
5 / 100
 308 ms 128740 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;
stack<int> updated;

int ft[200005];

int ls(int x) { return x & -x; }

int ft_qry(int p) {
	int r = 0;
	for (; p; p -= ls(p)) r += ft[p];
	return r;
}

void ft_upd(int p, int sz) {
	for (; p <= sz; p += ls(p)) {
		updated.push(p);
		ft[p]++;
	}
}

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;
	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;
	});
	vector<int> disc;
	for (auto [a, b, c] : sort_by) {
		if (c < 0) disc.pb(b);
		else disc.pb(c);
	}
	sort(disc.begin(), disc.end());
	disc.erase(unique(disc.begin(), disc.end()), disc.end());
	assert(disc.size() <= (int)2e5);
	while (!updated.empty()) {
		int cur = updated.top();
		ft[cur] = 0;
		updated.pop();
	}
	for (auto [a, b, c] : sort_by) {
		if (c < 0) {
			ans[-c] -= pf;
			assert(binary_search(disc.begin(), disc.end(), b));
			b = lower_bound(disc.begin(), disc.end(), b) - disc.begin() + 1;
			ans[-c] -= ft_qry(b);
		} else {
			pf += b;
			assert(binary_search(disc.begin(), disc.end(), c));
			c = lower_bound(disc.begin(), disc.end(), c) - disc.begin() + 1;
			ft_upd(c, (int)disc.size());
		}
	}
	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:136:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  136 | main() {
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 28936 KB Output is correct
2 Correct 25 ms 29036 KB Output is correct
3 Correct 31 ms 29796 KB Output is correct
4 Correct 42 ms 30164 KB Output is correct
5 Correct 198 ms 30540 KB Output is correct
6 Correct 203 ms 30496 KB Output is correct
7 Correct 256 ms 30524 KB Output is correct
8 Correct 27 ms 29908 KB Output is correct
9 Correct 26 ms 29780 KB Output is correct
10 Correct 27 ms 29736 KB Output is correct
11 Correct 28 ms 29700 KB Output is correct
12 Correct 35 ms 29908 KB Output is correct
13 Correct 39 ms 29896 KB Output is correct
14 Correct 38 ms 29460 KB Output is correct
15 Correct 115 ms 30284 KB Output is correct
16 Correct 115 ms 30264 KB Output is correct
17 Correct 123 ms 30236 KB Output is correct
18 Correct 120 ms 30168 KB Output is correct
19 Correct 124 ms 30188 KB Output is correct
20 Correct 125 ms 30128 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 50252 KB Output is correct
2 Correct 308 ms 53156 KB Output is correct
3 Correct 287 ms 50456 KB Output is correct
4 Runtime error 252 ms 128740 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 28936 KB Output is correct
2 Correct 25 ms 29036 KB Output is correct
3 Correct 31 ms 29796 KB Output is correct
4 Correct 42 ms 30164 KB Output is correct
5 Correct 198 ms 30540 KB Output is correct
6 Correct 203 ms 30496 KB Output is correct
7 Correct 256 ms 30524 KB Output is correct
8 Correct 27 ms 29908 KB Output is correct
9 Correct 26 ms 29780 KB Output is correct
10 Correct 27 ms 29736 KB Output is correct
11 Correct 28 ms 29700 KB Output is correct
12 Correct 35 ms 29908 KB Output is correct
13 Correct 39 ms 29896 KB Output is correct
14 Correct 38 ms 29460 KB Output is correct
15 Correct 115 ms 30284 KB Output is correct
16 Correct 115 ms 30264 KB Output is correct
17 Correct 123 ms 30236 KB Output is correct
18 Correct 120 ms 30168 KB Output is correct
19 Correct 124 ms 30188 KB Output is correct
20 Correct 125 ms 30128 KB Output is correct
21 Correct 195 ms 50252 KB Output is correct
22 Correct 308 ms 53156 KB Output is correct
23 Correct 287 ms 50456 KB Output is correct
24 Runtime error 252 ms 128740 KB Execution killed with signal 6
25 Halted 0 ms 0 KB -