oj.uz

답안 #715808

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
715808 2023-03-28T02:06:21 Z pavement 수확 (JOI20_harvest) C++17
5 / 100
 5000 ms 94884 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[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 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);
	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;
			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));
				}
			}
		}
	}
	// 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:136:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  136 | main() {
      | ^~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 28936 KB Output is correct
2 Correct 26 ms 29180 KB Output is correct
3 Correct 29 ms 29740 KB Output is correct
4 Correct 36 ms 30092 KB Output is correct
5 Correct 194 ms 30500 KB Output is correct
6 Correct 197 ms 30620 KB Output is correct
7 Correct 223 ms 30748 KB Output is correct
8 Correct 32 ms 29700 KB Output is correct
9 Correct 26 ms 29780 KB Output is correct
10 Correct 27 ms 29748 KB Output is correct
11 Correct 27 ms 29780 KB Output is correct
12 Correct 37 ms 29944 KB Output is correct
13 Correct 36 ms 29900 KB Output is correct
14 Correct 34 ms 29524 KB Output is correct
15 Correct 115 ms 30312 KB Output is correct
16 Correct 118 ms 30320 KB Output is correct
17 Correct 113 ms 30312 KB Output is correct
18 Correct 120 ms 30132 KB Output is correct
19 Correct 120 ms 30092 KB Output is correct
20 Correct 114 ms 30232 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 50288 KB Output is correct
2 Correct 296 ms 53352 KB Output is correct
3 Correct 283 ms 50228 KB Output is correct
4 Correct 271 ms 65100 KB Output is correct
5 Execution timed out 5062 ms 94884 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 28936 KB Output is correct
2 Correct 26 ms 29180 KB Output is correct
3 Correct 29 ms 29740 KB Output is correct
4 Correct 36 ms 30092 KB Output is correct
5 Correct 194 ms 30500 KB Output is correct
6 Correct 197 ms 30620 KB Output is correct
7 Correct 223 ms 30748 KB Output is correct
8 Correct 32 ms 29700 KB Output is correct
9 Correct 26 ms 29780 KB Output is correct
10 Correct 27 ms 29748 KB Output is correct
11 Correct 27 ms 29780 KB Output is correct
12 Correct 37 ms 29944 KB Output is correct
13 Correct 36 ms 29900 KB Output is correct
14 Correct 34 ms 29524 KB Output is correct
15 Correct 115 ms 30312 KB Output is correct
16 Correct 118 ms 30320 KB Output is correct
17 Correct 113 ms 30312 KB Output is correct
18 Correct 120 ms 30132 KB Output is correct
19 Correct 120 ms 30092 KB Output is correct
20 Correct 114 ms 30232 KB Output is correct
21 Correct 191 ms 50288 KB Output is correct
22 Correct 296 ms 53352 KB Output is correct
23 Correct 283 ms 50228 KB Output is correct
24 Correct 271 ms 65100 KB Output is correct
25 Execution timed out 5062 ms 94884 KB Time limit exceeded
26 Halted 0 ms 0 KB -