oj.uz

Submission #715802

# Submission time Handle Problem Language Result Execution time Memory
715802 2023-03-28T01:40:15 Z pavement Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 84552 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));
	}
}

gp_hash_table<int, int> T2_ft;
gp_hash_table<int, ordered_set<ii> > T3_ft;

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

void T2_upd(int p, int v) {
	for (p += (int)1e18 / 2; p <= (int)1e18; p += ls(p)) {
		T2_ft[p] += v;
	}
}

int T2_qry(int p) {
	int r = 0;
	for (p += (int)1e18 / 2; p; p -= ls(p)) {
		if (T2_ft.find(p) != T2_ft.end()) {
			r += T2_ft[p];
		}
	}
	return r;
}

void T3_upd(int p, int v, int idx) {
	for (p += (int)1e18 / 2; p <= (int)1e18; p += ls(p)) {
		T3_ft[p].insert(mp(v, idx));
	}
}

int T3_qry(int p, int v) {
	int r = 0;
	for (p += (int)1e18 / 2; p; p -= ls(p)) {
		if (T3_ft.find(p) != T3_ft.end()) {
			r += T3_ft[p].order_of_key(mp(v, LLONG_MAX));
		}
	}
	return r;
}

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) {
			//~ cout << "@ " << -c << ' ' << l << ' ' << m << ' ' << r << ' ' << a << ' ' << b << ' ' << c << ' ' << pf << ' ' << O.order_of_key(mp(b, (int)LLONG_MAX)) << '\n';
			ans[-c] -= pf;
			ans[-c] -= O.order_of_key(mp(b, (int)LLONG_MAX));
		} else {
			//~ cout << "ADD " << a << ' ' << b << ' ' << c << '\n';
			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();
			T2_ft.clear();
			T3_ft.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));
					T2_upd(a, q2);
					T3_upd(a, len - r2, 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());
			//~ cout << "SIZEOF " << adds.size() << '\n';
			cdq(0, (int)adds.size() - 1);
			reverse(ord.begin(), ord.end());
			P = 0;
			T1.clear();
			T2_ft.clear();
			T3_ft.clear();
			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 C1 = q1 * T1.order_of_key(mp(b, LLONG_MAX));
					int C2 = -T2_qry(b);
					int C3 = -T3_qry(b, len - r1 - 1);
					ans[idx] += C1 + C2 + C3;
				}
				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));
					T2_upd(a, q2);
					T3_upd(a, len - r2, idx);
				}
			}
		}
	}
	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 27 ms 28884 KB Output is correct
2 Correct 93 ms 29112 KB Output is correct
3 Correct 93 ms 37848 KB Output is correct
4 Correct 801 ms 43712 KB Output is correct
5 Correct 2775 ms 56080 KB Output is correct
6 Correct 2766 ms 56560 KB Output is correct
7 Correct 2821 ms 55892 KB Output is correct
8 Correct 365 ms 44920 KB Output is correct
9 Correct 354 ms 45252 KB Output is correct
10 Correct 350 ms 44684 KB Output is correct
11 Correct 329 ms 44704 KB Output is correct
12 Correct 1324 ms 43632 KB Output is correct
13 Correct 4043 ms 55296 KB Output is correct
14 Correct 938 ms 36476 KB Output is correct
15 Correct 2108 ms 57008 KB Output is correct
16 Correct 2168 ms 57088 KB Output is correct
17 Correct 2164 ms 56632 KB Output is correct
18 Correct 2270 ms 56360 KB Output is correct
19 Correct 2273 ms 56380 KB Output is correct
20 Correct 2201 ms 56508 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 59760 KB Output is correct
2 Execution timed out 5015 ms 84552 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 28884 KB Output is correct
2 Correct 93 ms 29112 KB Output is correct
3 Correct 93 ms 37848 KB Output is correct
4 Correct 801 ms 43712 KB Output is correct
5 Correct 2775 ms 56080 KB Output is correct
6 Correct 2766 ms 56560 KB Output is correct
7 Correct 2821 ms 55892 KB Output is correct
8 Correct 365 ms 44920 KB Output is correct
9 Correct 354 ms 45252 KB Output is correct
10 Correct 350 ms 44684 KB Output is correct
11 Correct 329 ms 44704 KB Output is correct
12 Correct 1324 ms 43632 KB Output is correct
13 Correct 4043 ms 55296 KB Output is correct
14 Correct 938 ms 36476 KB Output is correct
15 Correct 2108 ms 57008 KB Output is correct
16 Correct 2168 ms 57088 KB Output is correct
17 Correct 2164 ms 56632 KB Output is correct
18 Correct 2270 ms 56360 KB Output is correct
19 Correct 2273 ms 56380 KB Output is correct
20 Correct 2201 ms 56508 KB Output is correct
21 Correct 246 ms 59760 KB Output is correct
22 Execution timed out 5015 ms 84552 KB Time limit exceeded
23 Halted 0 ms 0 KB -