Submission #212290

#	Time	Username	Problem	Language	Result	Execution time	Memory
212290		ksun48	Harvest (JOI20_harvest)	C++14	100 / 100	897 ms	132656 KiB

harvest

#include <bits/stdc++.h>
#include <bits/extc++.h> /** keep-include */
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

using namespace __gnu_pbds;

template<class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag,
	  tree_order_statistics_node_update>;

using ll = long long;

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll n, m, l, c;
	cin >> n >> m >> l >> c;
	vector<ll> next_vert(n);
	vector<ll> next_dist(n);
	vector<vector<ll> > when_add(n);
	{
		vector<ll> a(n);
		for(ll& x : a){
			cin >> x;
			x = (l-1) - x;
		}
		reverse(a.begin(), a.end());
		for(ll i = 0; i < n; i++){
			ll res = (((a[i] + c) % l) + l) % l;
			auto r = lower_bound(a.begin(), a.end(), res);
			if(r == a.end()){
				next_dist[i] = c + l + a.front() - res;
				next_vert[i] = 0;
			} else {
				next_dist[i] = c + *r - res;
				next_vert[i] = r - a.begin();
			}
		}
		vector<ll> b(m);
		for(ll& x : b){
			cin >> x;
			x = (l-1) - x;
		}
		for(ll x : b){
			ll res = x;
			auto r = lower_bound(a.begin(), a.end(), res);
			ll d;
			ll v;
			if(r == a.end()){
				d = l + a.front() - res;
				v = 0;
			} else {
				d = *r - res;
				v = r - a.begin();
			}
			when_add[v].push_back(d);
		}
	}

	vector<bool> cycle_start(n, false);
	vector<vector<ll> > children(n);
	vector<ll> root_dist(n);
	{
		vector<ll> seen(n, 0);
		for(ll i = 0; i < n; i++){
			ll cur = i;
			while(seen[cur] == 0){
				seen[cur] = 1;
				cur = next_vert[cur];
			}
			if(seen[cur] == 1){
				cycle_start[cur] = true;
			}
			cur = i;
			while(seen[cur] == 1){
				seen[cur] = 2;
				cur = next_vert[cur];
			}
		}
		for(ll i = 0; i < n; i++){
			if(!cycle_start[i]){
				children[next_vert[i]].push_back(i);
			}
		}
		for(ll i = 0; i < n; i++){
			if(!cycle_start[i]) continue;
			y_combinator([&](auto self, ll v, ll dist) -> void {
				root_dist[v] = dist;
				for(ll w : children[v]){
					self(w, dist + next_dist[w]);
				}
			})(i, 0);
		}
	}

	vector<vector<ll> > queries_loc(n);
	ll q;
	cin >> q;
	vector<ll> qv(q);
	vector<ll> qt(q);
	vector<ll> answer(q, 0);
	for(ll i = 0; i < q; i++){
		cin >> qv[i] >> qt[i];
		qv[i]--;
		qv[i] = n-1-qv[i];
		queries_loc[qv[i]].push_back(i);
	}
	// solve for tree first
	mt19937_64 mt(48);
	vector<Tree<pair<ll, unsigned long long> > > when(n);
	for(ll i = 0; i < n; i++){
		if(!cycle_start[i]) continue;
		ll loc = y_combinator([&](auto self, ll v) -> ll {
			ll cur = v;
			for(ll t : when_add[v]){
				when[v].insert({t + root_dist[v], mt()});
			}
			for(ll w : children[v]){
				ll g = self(w);
				if(when[cur].size() < when[g].size()) swap(cur, g);
				for(auto x : when[g]) when[cur].insert(x);
				when[g] = {};
			}
			for(ll idx : queries_loc[v]){
				answer[idx] += when[cur].order_of_key({qt[idx] + root_dist[v], -1});
			}
			return cur;
		})(i);

		vector<pair<ll, ll> > queries;

		ll len = next_dist[i] + root_dist[next_vert[i]];
		ll cur = i;
		while(true){
			for(ll idx : queries_loc[cur]){
				queries.push_back({qt[idx] - (len - root_dist[cur]), idx});
			}
			cur = next_vert[cur];
			if(cur == i) break;
		}
		for(auto x : when[loc]){
			queries.push_back({x.first, -1});
		}
		sort(queries.begin(), queries.end());
		Tree<pair<ll, unsigned long long> > f;
		ll del = 0;
		for(pair<ll, ll> qq : queries){
			if(qq.second == -1){
				f.insert({qq.first % len, mt()});
				del -= (qq.first / len);
			} else {
				answer[qq.second] += del + (qq.first / len) * (ll)(f.size()) + f.order_of_key({qq.first % len, -1});
			}
		}
	}
	for(ll i = 0; i < q; i++){
		cout << answer[i] << '\n';
	}
}

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