oj.uz

Submission #715806

# Submission time Handle Problem Language Result Execution time Memory
715806 2023-03-28T02:02:53 Z pavement Harvest (JOI20_harvest) C++17
5 / 100
 320 ms 125368 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());
	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;
			b = lower_bound(disc.begin(), disc.end(), b) - disc.begin() + 1;
			ans[-c] -= ft_qry(b);
		} else {
			pf += b;
			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:133:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  133 | main() {
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 28856 KB Output is correct
2 Correct 23 ms 29064 KB Output is correct
3 Correct 27 ms 29776 KB Output is correct
4 Correct 36 ms 30184 KB Output is correct
5 Correct 190 ms 30496 KB Output is correct
6 Correct 202 ms 30648 KB Output is correct
7 Correct 227 ms 30512 KB Output is correct
8 Correct 27 ms 29780 KB Output is correct
9 Correct 26 ms 29784 KB Output is correct
10 Correct 29 ms 29808 KB Output is correct
11 Correct 26 ms 29772 KB Output is correct
12 Correct 33 ms 29948 KB Output is correct
13 Correct 35 ms 29904 KB Output is correct
14 Correct 35 ms 29532 KB Output is correct
15 Correct 122 ms 30316 KB Output is correct
16 Correct 116 ms 30224 KB Output is correct
17 Correct 112 ms 30252 KB Output is correct
18 Correct 121 ms 30204 KB Output is correct
19 Correct 124 ms 30180 KB Output is correct
20 Correct 123 ms 30144 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 50280 KB Output is correct
2 Correct 301 ms 53168 KB Output is correct
3 Correct 231 ms 50328 KB Output is correct
4 Runtime error 320 ms 125368 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 28856 KB Output is correct
2 Correct 23 ms 29064 KB Output is correct
3 Correct 27 ms 29776 KB Output is correct
4 Correct 36 ms 30184 KB Output is correct
5 Correct 190 ms 30496 KB Output is correct
6 Correct 202 ms 30648 KB Output is correct
7 Correct 227 ms 30512 KB Output is correct
8 Correct 27 ms 29780 KB Output is correct
9 Correct 26 ms 29784 KB Output is correct
10 Correct 29 ms 29808 KB Output is correct
11 Correct 26 ms 29772 KB Output is correct
12 Correct 33 ms 29948 KB Output is correct
13 Correct 35 ms 29904 KB Output is correct
14 Correct 35 ms 29532 KB Output is correct
15 Correct 122 ms 30316 KB Output is correct
16 Correct 116 ms 30224 KB Output is correct
17 Correct 112 ms 30252 KB Output is correct
18 Correct 121 ms 30204 KB Output is correct
19 Correct 124 ms 30180 KB Output is correct
20 Correct 123 ms 30144 KB Output is correct
21 Correct 172 ms 50280 KB Output is correct
22 Correct 301 ms 53168 KB Output is correct
23 Correct 231 ms 50328 KB Output is correct
24 Runtime error 320 ms 125368 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -