Submission #242129

#	Time	Username	Problem	Language	Result	Execution time	Memory
242129		super_j6	Harvest (JOI20_harvest)	C++14	0 / 100	139 ms	23712 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<int, 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<int, int> mp;
	
	void clr(){
		s.clear();
		mp.clear();
	}
	
	void add(int x){
		s.insert({x, mp[x]++});
	}
	
	int qry(int x){
		return s.order_of_key({x + 1, -1});
	}
	
	int qry(int a, int b){
		return qry(b) - qry(a - 1);
	}
};

const int mxn = 200001;
int n, m, k, w, q;
int a[mxn], b[mxn];
ll p[mxn], rt[mxn], l[mxn], r[mxn], d[mxn];
bool vis[mxn], vis2[mxn];
vector<pii> qry;
vector<pii> qv[mxn];
vector<ll> g[mxn], v[mxn];
omset tre;
ll ans[mxn];
int s, t;

int dfs(int c){
	l[c] = r[c] = t++;
	for(int i : g[c]){
		if(~rt[i]) continue;
		d[i] = d[c] + (k + a[i] - a[c]) % k;
		rt[i] = rt[c];
		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) - a - 1) % n;
		g[p[i]].push_back(i);
	}
	
	for(int i = 0; i < n; i++){
		if(!vis[i]){
			int j;
			for(j = i; !vis[p[j]]; j = p[j]) vis[j] = vis2[j] = 1;
			if(vis2[p[j]]){
				for(int l = p[j]; l != j; l = p[l]){
					v[s].push_back(l);
					rt[l] = l;
				}
				v[s].push_back(j);
				rt[j] = j;
				s++;
			}
			for(int l = i; l != j; l = p[l]) vis2[l] = 0;
			vis2[j] = 0;
		}
	}
	
	for(int i = 0; i < s; i++)
	for(int j : v[i]){
		dfs(j);
	} 
	//end init graph
	
	cin >> q;
	
	for(int i = 0; i < q; i++){
		ll x, y;
		cin >> x >> y;
		x--;
		pii z = {d[x] + y, {i, x}};
		if(rt[x] == x) qv[x].push_back(z);
		qry.push_back(z);
	}
	
	for(int i = 0; i < m; i++){
		int x = (n + upper_bound(a, a + n, b[i]) - a - 1) % n;
		pii z = {d[x] + (k + b[i] - a[x]) % k, {-1, x}};
		qv[rt[x]].push_back(z);
		qry.push_back(z); 
	}
	
	sort(qry.begin(), qry.end());
	
	for(pii i : qry){
		if(!~i.s.f) tre.add(l[i.s.s]);
		else ans[i.s.f] = tre.qry(l[i.s.s], r[i.s.s]);
	}
	
	/*
	for(int i = 0; i < s; i++){
		qry.clear();
		tre.clr();
		for(int j : v[i])
		for(pii l : qv[j]){
			pii z = l;
			z.f += (k + a[j] - v[i][0]) % k;
			qry.push_back(z);
		}
		
		sort(qry.begin(), qry.end());
		
		ll dt = 0, len = (k + a[p[v[i][0]]] - a[v[i][0]]) % k;
		for(pii j : qry){
			if(!~j.s.f){
				dt -= j.f / len;
				tre.add(j.f % len);
			}else{
				ans[j.s.f] += dt + tre.qry(len) * (j.f / k) + tre.qry(j.f % len);
			}
		}
	}
	*/
	
	ans[0]++;
	for(int i = 0; i < q; i++) cout << ans[i] << endl;

	return 0;
}

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