oj.uz

Submission #715512

# Submission time Handle Problem Language Result Execution time Memory
715512 2023-03-27T04:59:04 Z pavement Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 33176 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> 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));
	}
}

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;
			//~ for (auto x : ord) {
				//~ cout << "AT " << x << '\n';
				//~ for (auto [v, _] : S[x]) {
					//~ v += off[x];
					//~ cout << "ADD " << ((P - v) % len + len) % len << '\n';
				//~ }
				//~ for (auto [t, idx] : qu[x]) {
					//~ int b = t - P + 1;
					//~ cout << "QUERY " << 0 << ' ' << (len - (b % len)) % len << '\n';
					//~ cout << "QUERY " << (len - (b % len)) % len + 1 << ' ' << len - 1 << '\n';
				//~ }
				//~ P += to[x].second;
			//~ }
			for (auto x : ord) {
				for (auto [t, idx] : qu[x]) {
					int cur = x, P = 0;
					do {
						P += to[cur].second;
						cur = to[cur].first;
						// dist cur -> x = len - P
						for (auto [v, _] : S[cur]) {
							v += off[cur];
							if (v + len - P <= t) {
								// find k s.t. v + len - P + len * k <= t
								// k <= (t - (v + len - P)) / len
								ans[idx] += (t - (v + len - P)) / len + 1;
							}
						}
					} while (cur != x);
				}
			}
		}
	}
	for (int i = 1; i <= Q; i++) {
		cout << ans[i] << '\n';
	}
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28628 KB Output is correct
2 Correct 23 ms 29072 KB Output is correct
3 Correct 111 ms 29092 KB Output is correct
4 Correct 32 ms 29524 KB Output is correct
5 Correct 188 ms 30168 KB Output is correct
6 Correct 193 ms 30228 KB Output is correct
7 Correct 195 ms 30156 KB Output is correct
8 Correct 25 ms 29264 KB Output is correct
9 Correct 24 ms 29268 KB Output is correct
10 Correct 25 ms 29516 KB Output is correct
11 Correct 26 ms 29512 KB Output is correct
12 Correct 116 ms 29164 KB Output is correct
13 Correct 161 ms 29240 KB Output is correct
14 Correct 67 ms 29212 KB Output is correct
15 Correct 106 ms 29900 KB Output is correct
16 Correct 109 ms 30028 KB Output is correct
17 Correct 126 ms 30072 KB Output is correct
18 Correct 132 ms 29796 KB Output is correct
19 Correct 113 ms 29772 KB Output is correct
20 Correct 116 ms 29840 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5006 ms 33176 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28628 KB Output is correct
2 Correct 23 ms 29072 KB Output is correct
3 Correct 111 ms 29092 KB Output is correct
4 Correct 32 ms 29524 KB Output is correct
5 Correct 188 ms 30168 KB Output is correct
6 Correct 193 ms 30228 KB Output is correct
7 Correct 195 ms 30156 KB Output is correct
8 Correct 25 ms 29264 KB Output is correct
9 Correct 24 ms 29268 KB Output is correct
10 Correct 25 ms 29516 KB Output is correct
11 Correct 26 ms 29512 KB Output is correct
12 Correct 116 ms 29164 KB Output is correct
13 Correct 161 ms 29240 KB Output is correct
14 Correct 67 ms 29212 KB Output is correct
15 Correct 106 ms 29900 KB Output is correct
16 Correct 109 ms 30028 KB Output is correct
17 Correct 126 ms 30072 KB Output is correct
18 Correct 132 ms 29796 KB Output is correct
19 Correct 113 ms 29772 KB Output is correct
20 Correct 116 ms 29840 KB Output is correct
21 Execution timed out 5006 ms 33176 KB Time limit exceeded
22 Halted 0 ms 0 KB -