Submission #213255

#	Time	Username	Problem	Language	Result	Execution time	Memory
213255		iefnah06	Harvest (JOI20_harvest)	C++14	100 / 100	967 ms	138328 KiB

harvest

#ifndef LOCAL
#define DEBUG
#endif
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

namespace std {

template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

} // namespace std

namespace __gnu_pbds {
template <typename K, typename V=null_type>
using order_statistic_tree = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;
}
using __gnu_pbds::order_statistic_tree;

using ll = long long;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

	int N, M, L, C; cin >> N >> M >> L >> C;
	auto Xtrans = [&](int x) -> int {
		return L-1-x;
	};
	vector<int> A(N);
	for (int& x : A) {
		cin >> x;
		x = Xtrans(x);
	}
	reverse(A.begin(), A.end());
	vector<int> B(M);
	for (int& x : B) {
		cin >> x;
		x = Xtrans(x);
	}

	vector<int> dest(N);
	vector<int> dist(N);
	for (int i = 0; i < N; i++) {
		int tgt = (A[i] + C) % L;
		auto it = lower_bound(A.begin(), A.end(), tgt);
		if (it == A.end()) {
			dest[i] = 0;
			dist[i] = C + L + A[0] - tgt;
		} else {
			dest[i] = int(distance(A.begin(), it));
			dist[i] = C + *it - tgt;
		}
	}

	vector<bool> vis(N, false);
	vector<bool> isRoot(N, false);
	for (int v = 0; v < N; v++) {
		if (vis[v]) continue;
		int t, h;
		for (t = dest[v], h = dest[dest[v]]; !vis[t] && t != h; t = dest[t], h = dest[dest[h]]) {}

		if (!vis[t]) {
			isRoot[t] = true;
			for (int cur = dest[t]; true; cur = dest[cur]) {
				vis[cur] = true;
				if (cur == t) break;
			}
		}

		for (int cur = v; cur != t; cur = dest[cur]) {
			vis[cur] = true;
		}
	}

	vector<vector<int>> evtsAdd(N);
	for (int i = 0; i < M; i++) {
		auto it = lower_bound(A.begin(), A.end(), B[i]);
		if (it == A.end()) {
			evtsAdd[0].push_back(L + A[0] - B[i]);
		} else {
			evtsAdd[distance(A.begin(), it)].push_back(*it - B[i]);
		}
	}

	int Q; cin >> Q;
	vector<int> V(Q);
	vector<ll> T(Q);
	vector<vector<int>> queriesLoc(N);
	for (int i = 0; i < Q; i++) {
		cin >> V[i] >> T[i];
		V[i]--;
		V[i] = N-1-V[i];
		queriesLoc[V[i]].push_back(i);
	}

	vector<ll> ans(Q);

	vector<vector<int>> ch(N);
	for (int v = 0; v < N; v++) {
		if (!isRoot[v]) {
			ch[dest[v]].push_back(v);
		}
	}
	vector<ll> depth(N);
	for (int v = 0; v < N; v++) {
		if (!isRoot[v]) continue;
		y_combinator([&](auto self, int cur, ll curDepth) -> void {
			depth[cur] = curDepth;
			for (int nxt : ch[cur]) {
				self(nxt, curDepth + dist[nxt]);
			}
		})(v, 0);
	}
	mt19937_64 mt(114514);
	using tree_t = order_statistic_tree<pair<ll, unsigned long long>>;
	vector<tree_t> evtTree(N);
	for (int v = 0; v < N; v++) {
		if (!isRoot[v]) continue;

		int treeInd = y_combinator([&](auto self, int cur) -> int {
			int res = cur;
			for (auto t : evtsAdd[cur]) {
				evtTree[res].insert({t + depth[cur], mt()});
			}

			for (int nxt : ch[cur]) {
				int nres = self(nxt);
				if (evtTree[res].size() < evtTree[nres].size()) swap(res, nres);
				for (auto t : evtTree[nres]) {
					evtTree[res].insert(t);
				}
				evtTree[nres] = {};
			}

			for (int it : queriesLoc[cur]) {
				ans[it] += evtTree[res].order_of_key({T[it] + depth[cur], -1});
			}

			return res;
		})(v);

		ll cycLen = dist[v] + depth[dest[v]];

		vector<pair<ll, int>> toProcess;
		for (auto t : evtTree[treeInd]) {
			toProcess.emplace_back(t.first, -1);
		}
		for (int cur = dest[v]; true; cur = dest[cur]) {
			for (auto it : queriesLoc[cur]) {
				toProcess.emplace_back(T[it] - (cycLen - depth[cur]), it);
			}
			if (cur == v) break;
		}
		sort(toProcess.begin(), toProcess.end());

		tree_t tr;
		ll delta = 0;
		for (auto it : toProcess) {
			ll val = it.first;
			int ind = it.second;
			if (ind == -1) {
				delta -= val / cycLen;
				tr.insert({val % cycLen, mt()});
			} else {
				ans[ind] += delta + ll(tr.size()) * (val / cycLen) + tr.order_of_key({val % cycLen, -1});
			}
		}
	}

	for (ll v : ans) {
		cout << v << '\n';
	}

	return 0;
}

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