oj.uz

Submission #715812

# Submission time Handle Problem Language Result Execution time Memory
715812 2023-03-28T05:51:47 Z pavement Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 118432 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], nS[200005];
ordered_set<ii> 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<iii> adds[400005], qus[400005];
stack<int> updated;

int ft[400005];

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 ft_reset() {
	while (!updated.empty()) {
		int cur = updated.top();
		ft[cur] = 0;
		updated.pop();
	}
}

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)4e5);
	ft_reset();
	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));
				}
			}
			for (auto [v, idx] : S[i]) {
				nS[i].eb(v, idx);
			}
		}
	}
	// 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, cnt = 0;
			vector<int> disc;
			ft_reset();
			qus[0].clear();
			for (auto x : ord) {
				adds[cnt].clear();
				for (auto [v, idx] : nS[x]) {
					int a = v + off[x] - P;
					int q2 = a / len, r2 = a % len;
					if (r2 < 0) {
						r2 += len;
						q2--;
					}
					adds[cnt].eb(a, q2, len - r2);
					disc.pb(a);
				}
				qus[cnt + 1].clear();
				for (auto [t, idx] : qu[x]) {
					int b = t - P + len;
					int q1 = b / len, r1 = b % len;
					if (r1 < 0) {
						r1 += len;
						q1--;
					}
					qus[cnt + 1].eb(b, len - r1 - 1, idx);
					disc.pb(b);
				}
				P += to[x].second;
				cnt++;
			}
			P = 0;
			sort(disc.begin(), disc.end());
			disc.erase(unique(disc.begin(), disc.end()), disc.end());
			for (auto x : ord) {
				for (auto [v, idx] : nS[x]) {
					int a = v + off[x] - P;
					int da = lower_bound(disc.begin(), disc.end(), a) - disc.begin() + 1;
					ft_upd(da, (int)disc.size());
				}
				for (auto [t, idx] : qu[x]) {
					int b = t - P + len;
					int q1 = b / len, r1 = b % len;
					if (r1 < 0) {
						r1 += len;
						q1--;
					}
					int db = lower_bound(disc.begin(), disc.end(), b) - disc.begin() + 1;
					ans[idx] += q1 * ft_qry(db);
				}
				P += to[x].second;
			}
			adds[cnt].clear();
			cnt++;
			if (cnt) cdq(0, cnt - 1);
			reverse(ord.begin(), ord.end());
			P = cnt = 0;
			disc.clear();
			ft_reset();
			for (auto x : ord) {
				adds[cnt].clear();
				qus[cnt].clear();
				P += to[x].second;
				for (auto [v, idx] : nS[x]) {
					int a = v + off[x] + P;
					int q2 = a / len, r2 = a % len;
					if (r2 < 0) {
						r2 += len;
						q2--;
					}
					disc.pb(a);
					adds[cnt].eb(a, q2, len - r2);
				}
				for (auto [t, idx] : qu[x]) {
					int b = t + P;
					int q1 = b / len, r1 = b % len;
					if (r1 < 0) {
						r1 += len;
						q1--;
					}
					qus[cnt].eb(b, len - r1 - 1, idx);
					disc.pb(b);
				}
				cnt++;
			}
			P = 0;
			sort(disc.begin(), disc.end());
			disc.erase(unique(disc.begin(), disc.end()), disc.end());
			for (auto x : ord) {
				P += to[x].second;
				for (auto [t, idx] : qu[x]) {
					int b = t + P;
					int q1 = b / len, r1 = b % len;
					if (r1 < 0) {
						r1 += len;
						q1--;
					}
					int db = lower_bound(disc.begin(), disc.end(), b) - disc.begin() + 1;
					ans[idx] += q1 * ft_qry(db);
				}
				for (auto [v, idx] : nS[x]) {
					int a = v + off[x] + P;
					int da = lower_bound(disc.begin(), disc.end(), a) - disc.begin() + 1;
					ft_upd(da, (int)disc.size());
				}
			}
			if (cnt) cdq(0, cnt - 1);
		}
	}
	for (int i = 1; i <= Q; i++) {
		cout << ans[i] << '\n';
	}
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 52436 KB Output is correct
2 Correct 44 ms 52636 KB Output is correct
3 Correct 43 ms 53252 KB Output is correct
4 Correct 51 ms 53668 KB Output is correct
5 Correct 238 ms 54076 KB Output is correct
6 Correct 215 ms 54028 KB Output is correct
7 Correct 237 ms 54092 KB Output is correct
8 Correct 41 ms 53160 KB Output is correct
9 Correct 41 ms 53144 KB Output is correct
10 Correct 39 ms 53204 KB Output is correct
11 Correct 40 ms 53248 KB Output is correct
12 Correct 49 ms 53332 KB Output is correct
13 Correct 53 ms 53432 KB Output is correct
14 Correct 47 ms 53064 KB Output is correct
15 Correct 124 ms 53816 KB Output is correct
16 Correct 128 ms 53828 KB Output is correct
17 Correct 137 ms 53768 KB Output is correct
18 Correct 144 ms 53648 KB Output is correct
19 Correct 133 ms 53680 KB Output is correct
20 Correct 151 ms 53760 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 79220 KB Output is correct
2 Correct 319 ms 76668 KB Output is correct
3 Correct 241 ms 73992 KB Output is correct
4 Correct 368 ms 93300 KB Output is correct
5 Execution timed out 5051 ms 118432 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 52436 KB Output is correct
2 Correct 44 ms 52636 KB Output is correct
3 Correct 43 ms 53252 KB Output is correct
4 Correct 51 ms 53668 KB Output is correct
5 Correct 238 ms 54076 KB Output is correct
6 Correct 215 ms 54028 KB Output is correct
7 Correct 237 ms 54092 KB Output is correct
8 Correct 41 ms 53160 KB Output is correct
9 Correct 41 ms 53144 KB Output is correct
10 Correct 39 ms 53204 KB Output is correct
11 Correct 40 ms 53248 KB Output is correct
12 Correct 49 ms 53332 KB Output is correct
13 Correct 53 ms 53432 KB Output is correct
14 Correct 47 ms 53064 KB Output is correct
15 Correct 124 ms 53816 KB Output is correct
16 Correct 128 ms 53828 KB Output is correct
17 Correct 137 ms 53768 KB Output is correct
18 Correct 144 ms 53648 KB Output is correct
19 Correct 133 ms 53680 KB Output is correct
20 Correct 151 ms 53760 KB Output is correct
21 Correct 288 ms 79220 KB Output is correct
22 Correct 319 ms 76668 KB Output is correct
23 Correct 241 ms 73992 KB Output is correct
24 Correct 368 ms 93300 KB Output is correct
25 Execution timed out 5051 ms 118432 KB Time limit exceeded
26 Halted 0 ms 0 KB -