Submission #242350

#	Time	Username	Problem	Language	Result	Execution time	Memory
242350		super_j6	Harvest (JOI20_harvest)	C++14	100 / 100	842 ms	73928 KiB

harvest

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<ll, int>
#define pii pair<ll, pi>
#define f first
#define s second

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

typedef tree<pi, null_type,less<pi>, rb_tree_tag,
	tree_order_statistics_node_update> oset;
	
struct omset{
	oset s;
	map<ll, int> mp;
	
	void clr(){
		s.clear();
		mp.clear();
	}
	
	void add(ll x){
		s.insert({x, mp[x]++});
	}
	
	int qry(ll x){
		return s.order_of_key({x + 1, -1});
	}
	
	int qry(ll a, ll b){
		return qry(b) - qry(a - 1);
	}
};

const int mxn = 200001;
ll n, m, k, w, q;
ll a[mxn], b[mxn];
ll rt[mxn], vis[mxn], p[mxn], d[mxn], l[mxn], r[mxn];
vector<pii> qr[mxn];
vector<int> g[mxn];
omset tre;
ll ans[mxn];

ll dst(int x, int y){
	return w + (k + a[y] - (a[x] + w) % k) % k;
}

int dfs(int c){
	r[c] = l[c];
	for(int i : g[c]){
		if(~rt[i]) continue;
		d[i] = d[c] + dst(c, i);
		rt[i] = rt[c];
		l[i] = r[c] + 1;
		r[c] = dfs(i);
	}
	return r[c];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> k >> w;
	
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < m; i++) cin >> b[i];
	
	//init graph
	for(int i = 0; i < n; i++){
		rt[i] = -1;
		p[i] = (n + upper_bound(a, a + n, (k + (a[i] - w) % k) % k) - a - 1) % n;
		g[p[i]].push_back(i);
	}
	
	for(int i = 0; i < n; i++){
		if(!~rt[i]){
			int j;
			for(j = i; !vis[j]; j = p[j]) vis[j] = 1;
			for(int l = i; l != j; l = p[l]) vis[l] = 0;
			
			rt[j] = j;
			dfs(j);
		}
	}
	//end init graph
	
	cin >> q;
	
	//init queries
	for(int i = 0; i < q; i++){
		ll x, y;
		cin >> x >> y;
		x--;
		qr[rt[x]].push_back({d[x] + y, {i, x}});
	}
	
	for(int i = 0; i < m; i++){
		int x = (n + upper_bound(a, a + n, b[i]) - a - 1) % n;
		qr[rt[x]].push_back({d[x] + (k + b[i] - a[x]) % k, {-1, x}});
	}
	//end init queries
	
	for(int i = 0; i < n; i++){
		if(rt[i] != i) continue;
		tre.clr();
		sort(qr[i].begin(), qr[i].end());
		
		//solve tree
		ll len = d[p[i]] + dst(p[i], i);
		for(pii &j : qr[i]){
			if(!~j.s.f){
				tre.add(l[j.s.s]);
			}else{
				ans[j.s.f] = tre.qry(l[j.s.s], r[j.s.s]);
				j.f -= len;
			}
		}
		
		tre.clr();
		sort(qr[i].begin(), qr[i].end());
		
		//solve cycle
		ll dt = 0;
		for(pii j : qr[i]){
			if(!~j.s.f){
				dt -= j.f / len;
				tre.add(j.f % len);
			}else if(vis[j.s.s]){
				ans[j.s.f] += dt + tre.qry(len) * (j.f / len) + tre.qry(j.f % len);
			}
		}
	}
	
	for(int i = 0; i < q; i++) cout << ans[i] << endl;

	return 0;
}

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