Submission #715902

#	Time	Username	Problem	Language	Result	Execution time	Memory
715902		pavement	Harvest (JOI20_harvest)	C++17	100 / 100	1968 ms	154644 KiB

harvest

#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 (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 75 / 75