oj.uz

Submission #715902

# Submission time Handle Problem Language Result Execution time Memory
715902 2023-03-28T11:34:21 Z pavement Harvest (JOI20_harvest) C++17
100 / 100
 1968 ms 154644 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, root, A[200005], B[200005], off[200005], lnk[200005], sz[200005], ans[200005];
bool on_cycle[200005];
ii to[200005];
vector<int> S[200005];
vector<ii> adj[200005], qu[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;
}

template <class T>
struct wavelet_matrix {
    using size_type = uint32_t;
    struct bit_vector {
        static constexpr size_type wsize = 64;
        static size_type rank64(uint64_t x, size_type i) {
            return __builtin_popcountll(x & ((1ULL << i) - 1));
        }
#pragma pack(4)
        struct block_t {
            uint64_t bit;
            size_type sum;
        };
#pragma pack()
        size_type n, zeros;
        vector<block_t> block;
        bit_vector(size_type _n = 0) : n(_n), block(n / wsize + 1) {}
        int operator[](size_type i) const {
            return block[i / wsize].bit >> i % wsize & 1;
        }
        void set(size_type i) {
            block[i / wsize].bit |= (uint64_t)1 << i % wsize;
        }
        void build() {
            for (size_type j = 0; j < n / wsize; ++j)
                block[j + 1].sum =
                    block[j].sum + __builtin_popcountll(block[j].bit);
            zeros = rank0(n);
        }
        size_type rank0(size_type i) const { return i - rank1(i); }
        size_type rank1(size_type i) const {
            auto&& e = block[i / wsize];
            return e.sum + rank64(e.bit, i % wsize);
        }
    };
    size_type n, lg;
    vector<T> a;
    vector<bit_vector> bv;
    wavelet_matrix(size_type _n = 0) : n(_n), a(n) {}
    wavelet_matrix(const vector<T>& _a) : n(_a.size()), a(_a) { build(); }
    T& operator[](size_type i) { return a[i]; }
    void build() {
        lg = __lg(max<T>(
                 *max_element(begin(a), end(a)), 1)) +
             1;
        bv.assign(lg, n);
        vector<T> cur = a, nxt(n);
        for (auto h = lg; h--;) {
            for (size_type i = 0; i < n; ++i)
                if (cur[i] >> h & 1) bv[h].set(i);
            bv[h].build();
            array it{begin(nxt), begin(nxt) + bv[h].zeros};
            for (size_type i = 0; i < n; ++i) *it[bv[h][i]]++ = cur[i];
            swap(cur, nxt);
        }
    }
    // find kth element in [l, r), 0 indexed
    T kth(size_type l, size_type r, size_type k) const {
        T res = 0;
        for (auto h = lg; h--;) {
            auto l0 = bv[h].rank0(l), r0 = bv[h].rank0(r);
            if (k < r0 - l0)
                l = l0, r = r0;
            else {
                k -= r0 - l0;
                res |= (T)1 << h;
                l += bv[h].zeros - l0;
                r += bv[h].zeros - r0;
            }
        }
        return res;
    }
    // count i in [l..r) satisfying a[i] < ub
    size_type count(size_type l, size_type r, T ub) const {
        if (ub >= (T)1 << lg) return r - l;
        size_type res = 0;
        for (auto h = lg; h--;) {
            auto l0 = bv[h].rank0(l), r0 = bv[h].rank0(r);
            if (~ub >> h & 1)
                l = l0, r = r0;
            else {
                res += r0 - l0;
                l += bv[h].zeros - l0;
                r += bv[h].zeros - r0;
            }
        }
        return res;
    }
    size_type count(size_type l, size_type r, T lb, T ub) const {
        return count(l, r, ub) - count(l, r, lb);
    }
};

template <class T>
auto zip(const vector<T>& a) {
    int n = size(a);
    vector<pair<T, int>> p(n);
    for (int i = 0; i < n; ++i) p[i] = {a[i], i};
    sort(begin(p), end(p));
    vector<int> na(n);
    vector<T> v;
    for (int k = 0, rnk = -1; k < n; ++k) {
        if (k == 0 or p[k - 1].first < p[k].first)
            v.push_back(p[k].first), ++rnk;
        na[p[k].second] = rnk;
    }
    return make_pair(na, v);
}

vector<int> wav;
vector<iiii> to_qry;

void solve_tree(int n, int d) {
	assert(!on_cycle[n]);
	int lb = (int)wav.size();
	for (auto v : S[n]) {
		wav.pb(v + d);
		S[root].pb(v + d);
	}
	for (auto [u, w] : adj[n]) {
		solve_tree(u, d + w);
	}
	for (auto [v, idx] : qu[n]) {
		to_qry.eb(lb, (int)wav.size(), v + d + 1, idx);
	}
}

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());
	ft_reset();
	for (auto [a, b, c] : sort_by) {
		if (c < 0) {
			b = lower_bound(disc.begin(), disc.end(), b) - disc.begin() + 1;
			ans[-c] -= ft_qry(b) + pf;
		} else {
			pf += b;
			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].pb(B[i] + L - A[N]);
		} else {
			--it;
			S[it - A].pb(B[i] - *it);
		}
	}
	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]) {
			root = i;
			wav.clear();
			to_qry.clear();
			for (auto [u, w] : adj[i]) if (!on_cycle[u]) {
				solve_tree(u, w);
			}
			if (wav.empty()) continue;
			auto [na, v] = zip(wav);
			wavelet_matrix wm(na);
			for (auto [l, r, k, idx] : to_qry) {
				if (l < r) {
					ans[idx] += wm.count(l, r, lower_bound(v.begin(), v.end(), k) - v.begin());
				}
			}
		}
	}
	// 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 : S[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 : S[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 : S[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 : S[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:246:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  246 | main() {
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 33620 KB Output is correct
2 Correct 20 ms 33556 KB Output is correct
3 Correct 22 ms 34240 KB Output is correct
4 Correct 23 ms 34432 KB Output is correct
5 Correct 21 ms 34640 KB Output is correct
6 Correct 24 ms 34612 KB Output is correct
7 Correct 23 ms 34596 KB Output is correct
8 Correct 26 ms 34148 KB Output is correct
9 Correct 20 ms 34232 KB Output is correct
10 Correct 20 ms 34192 KB Output is correct
11 Correct 20 ms 34248 KB Output is correct
12 Correct 30 ms 34388 KB Output is correct
13 Correct 33 ms 34360 KB Output is correct
14 Correct 30 ms 34104 KB Output is correct
15 Correct 22 ms 34356 KB Output is correct
16 Correct 22 ms 34388 KB Output is correct
17 Correct 22 ms 34388 KB Output is correct
18 Correct 21 ms 34368 KB Output is correct
19 Correct 20 ms 34388 KB Output is correct
20 Correct 22 ms 34372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 60284 KB Output is correct
2 Correct 214 ms 58256 KB Output is correct
3 Correct 220 ms 54936 KB Output is correct
4 Correct 337 ms 74288 KB Output is correct
5 Correct 207 ms 86980 KB Output is correct
6 Correct 200 ms 87032 KB Output is correct
7 Correct 185 ms 58412 KB Output is correct
8 Correct 178 ms 58332 KB Output is correct
9 Correct 1028 ms 76024 KB Output is correct
10 Correct 1968 ms 154644 KB Output is correct
11 Correct 1130 ms 76168 KB Output is correct
12 Correct 1150 ms 76172 KB Output is correct
13 Correct 1118 ms 76276 KB Output is correct
14 Correct 1430 ms 128496 KB Output is correct
15 Correct 974 ms 67496 KB Output is correct
16 Correct 213 ms 74392 KB Output is correct
17 Correct 196 ms 74264 KB Output is correct
18 Correct 132 ms 53872 KB Output is correct
19 Correct 126 ms 53740 KB Output is correct
20 Correct 182 ms 58892 KB Output is correct

Subtask #3
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 33620 KB Output is correct
2 Correct 20 ms 33556 KB Output is correct
3 Correct 22 ms 34240 KB Output is correct
4 Correct 23 ms 34432 KB Output is correct
5 Correct 21 ms 34640 KB Output is correct
6 Correct 24 ms 34612 KB Output is correct
7 Correct 23 ms 34596 KB Output is correct
8 Correct 26 ms 34148 KB Output is correct
9 Correct 20 ms 34232 KB Output is correct
10 Correct 20 ms 34192 KB Output is correct
11 Correct 20 ms 34248 KB Output is correct
12 Correct 30 ms 34388 KB Output is correct
13 Correct 33 ms 34360 KB Output is correct
14 Correct 30 ms 34104 KB Output is correct
15 Correct 22 ms 34356 KB Output is correct
16 Correct 22 ms 34388 KB Output is correct
17 Correct 22 ms 34388 KB Output is correct
18 Correct 21 ms 34368 KB Output is correct
19 Correct 20 ms 34388 KB Output is correct
20 Correct 22 ms 34372 KB Output is correct
21 Correct 248 ms 60284 KB Output is correct
22 Correct 214 ms 58256 KB Output is correct
23 Correct 220 ms 54936 KB Output is correct
24 Correct 337 ms 74288 KB Output is correct
25 Correct 207 ms 86980 KB Output is correct
26 Correct 200 ms 87032 KB Output is correct
27 Correct 185 ms 58412 KB Output is correct
28 Correct 178 ms 58332 KB Output is correct
29 Correct 1028 ms 76024 KB Output is correct
30 Correct 1968 ms 154644 KB Output is correct
31 Correct 1130 ms 76168 KB Output is correct
32 Correct 1150 ms 76172 KB Output is correct
33 Correct 1118 ms 76276 KB Output is correct
34 Correct 1430 ms 128496 KB Output is correct
35 Correct 974 ms 67496 KB Output is correct
36 Correct 213 ms 74392 KB Output is correct
37 Correct 196 ms 74264 KB Output is correct
38 Correct 132 ms 53872 KB Output is correct
39 Correct 126 ms 53740 KB Output is correct
40 Correct 182 ms 58892 KB Output is correct
41 Correct 863 ms 114044 KB Output is correct
42 Correct 272 ms 60108 KB Output is correct
43 Correct 289 ms 71216 KB Output is correct
44 Correct 437 ms 104592 KB Output is correct
45 Correct 370 ms 128748 KB Output is correct
46 Correct 383 ms 135948 KB Output is correct
47 Correct 399 ms 136656 KB Output is correct
48 Correct 405 ms 134688 KB Output is correct
49 Correct 366 ms 135172 KB Output is correct
50 Correct 345 ms 108208 KB Output is correct
51 Correct 369 ms 107996 KB Output is correct
52 Correct 1616 ms 121648 KB Output is correct
53 Correct 1705 ms 121548 KB Output is correct
54 Correct 1593 ms 121700 KB Output is correct
55 Correct 1631 ms 121756 KB Output is correct
56 Correct 466 ms 122708 KB Output is correct
57 Correct 458 ms 123596 KB Output is correct
58 Correct 470 ms 124336 KB Output is correct
59 Correct 414 ms 121708 KB Output is correct
60 Correct 418 ms 122352 KB Output is correct
61 Correct 491 ms 122572 KB Output is correct
62 Correct 1597 ms 102840 KB Output is correct
63 Correct 331 ms 99204 KB Output is correct
64 Correct 339 ms 99300 KB Output is correct
65 Correct 353 ms 99476 KB Output is correct
66 Correct 334 ms 99200 KB Output is correct
67 Correct 326 ms 99252 KB Output is correct
68 Correct 338 ms 98620 KB Output is correct
69 Correct 827 ms 108604 KB Output is correct
70 Correct 823 ms 105884 KB Output is correct
71 Correct 740 ms 123060 KB Output is correct
72 Correct 829 ms 152144 KB Output is correct