oj.uz

Submission #242151

# Submission time Handle Problem Language Result Execution time Memory
242151 2020-06-27T02:06:32 Z super_j6 Harvest (JOI20_harvest) C++14
0 / 100
 247 ms 33716 KB 
#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;
ll 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;

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

int dfs(int c){
	vis2[c] = 1;
	l[c] = r[c] = t++;
	for(int i : g[c]){
		if(vis2[i]) continue;
		d[i] = d[c] + dst(c, i);
		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) % 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++) dfs(v[i][0]);
	//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();
		
		ll len = d[v[i].back()] + dst(v[i][0], v[i].back());
		for(int j : v[i])
		for(pii l : qv[j]){
			qry.push_back(l);
			if(~qry.back().s.f) qry.back().f -= len;
		}
		
		sort(qry.begin(), qry.end());
		
		ll dt = 0;
		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 / len) + tre.qry(j.f % len);
			}
		}
	}
	
	for(int i = 0; i < q; i++) cout << ans[i] << endl;

	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14720 KB Output is correct
2 Correct 17 ms 15360 KB Output is correct
3 Correct 18 ms 15360 KB Output is correct
4 Correct 19 ms 15232 KB Output is correct
5 Correct 18 ms 15360 KB Output is correct
6 Correct 18 ms 15360 KB Output is correct
7 Correct 17 ms 15360 KB Output is correct
8 Correct 17 ms 15104 KB Output is correct
9 Correct 23 ms 15232 KB Output is correct
10 Correct 17 ms 15232 KB Output is correct
11 Correct 17 ms 15104 KB Output is correct
12 Correct 18 ms 15312 KB Output is correct
13 Incorrect 18 ms 15360 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 26184 KB Output is correct
2 Incorrect 247 ms 33716 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14720 KB Output is correct
2 Correct 17 ms 15360 KB Output is correct
3 Correct 18 ms 15360 KB Output is correct
4 Correct 19 ms 15232 KB Output is correct
5 Correct 18 ms 15360 KB Output is correct
6 Correct 18 ms 15360 KB Output is correct
7 Correct 17 ms 15360 KB Output is correct
8 Correct 17 ms 15104 KB Output is correct
9 Correct 23 ms 15232 KB Output is correct
10 Correct 17 ms 15232 KB Output is correct
11 Correct 17 ms 15104 KB Output is correct
12 Correct 18 ms 15312 KB Output is correct
13 Incorrect 18 ms 15360 KB Output isn't correct
14 Halted 0 ms 0 KB -