oj.uz

Submission #715788

# Submission time Handle Problem Language Result Execution time Memory
715788 2023-03-28T01:02:36 Z pavement Harvest (JOI20_harvest) C++17
0 / 100
 5000 ms 56624 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;
}

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();
			for (auto x : ord) {
				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 (auto [t, idx] : qu[x]) {
					int b = t - P + len;
					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;
				}
				P += to[x].second;
			}
			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:102:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  102 | main() {
      | ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 28756 KB Output is correct
2 Correct 126 ms 29140 KB Output is correct
3 Correct 616 ms 37996 KB Output is correct
4 Correct 795 ms 43748 KB Output is correct
5 Correct 2801 ms 56216 KB Output is correct
6 Correct 2798 ms 56624 KB Output is correct
7 Correct 2759 ms 56004 KB Output is correct
8 Correct 429 ms 44924 KB Output is correct
9 Correct 319 ms 45272 KB Output is correct
10 Correct 360 ms 44748 KB Output is correct
11 Correct 354 ms 44712 KB Output is correct
12 Correct 2033 ms 43476 KB Output is correct
13 Execution timed out 5049 ms 54952 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 787 ms 49188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 28756 KB Output is correct
2 Correct 126 ms 29140 KB Output is correct
3 Correct 616 ms 37996 KB Output is correct
4 Correct 795 ms 43748 KB Output is correct
5 Correct 2801 ms 56216 KB Output is correct
6 Correct 2798 ms 56624 KB Output is correct
7 Correct 2759 ms 56004 KB Output is correct
8 Correct 429 ms 44924 KB Output is correct
9 Correct 319 ms 45272 KB Output is correct
10 Correct 360 ms 44748 KB Output is correct
11 Correct 354 ms 44712 KB Output is correct
12 Correct 2033 ms 43476 KB Output is correct
13 Execution timed out 5049 ms 54952 KB Time limit exceeded
14 Halted 0 ms 0 KB -