oj.uz

Submission #242349

# Submission time Handle Problem Language Result Execution time Memory
242349 2020-06-27T09:16:41 Z super_j6 Harvest (JOI20_harvest) C++14
0 / 100
 344 ms 42864 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<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 != p[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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9984 KB Output is correct
2 Correct 15 ms 10240 KB Output is correct
3 Correct 16 ms 10684 KB Output is correct
4 Correct 16 ms 10688 KB Output is correct
5 Correct 15 ms 10684 KB Output is correct
6 Correct 16 ms 10684 KB Output is correct
7 Correct 16 ms 10812 KB Output is correct
8 Correct 16 ms 10572 KB Output is correct
9 Correct 15 ms 10572 KB Output is correct
10 Correct 15 ms 10572 KB Output is correct
11 Correct 16 ms 10572 KB Output is correct
12 Correct 15 ms 10684 KB Output is correct
13 Incorrect 16 ms 10684 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 20056 KB Output is correct
2 Correct 261 ms 32216 KB Output is correct
3 Correct 225 ms 32380 KB Output is correct
4 Correct 253 ms 33424 KB Output is correct
5 Correct 237 ms 41052 KB Output is correct
6 Correct 222 ms 41048 KB Output is correct
7 Correct 220 ms 27464 KB Output is correct
8 Correct 216 ms 27488 KB Output is correct
9 Correct 282 ms 42864 KB Output is correct
10 Correct 258 ms 42804 KB Output is correct
11 Incorrect 344 ms 41700 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9984 KB Output is correct
2 Correct 15 ms 10240 KB Output is correct
3 Correct 16 ms 10684 KB Output is correct
4 Correct 16 ms 10688 KB Output is correct
5 Correct 15 ms 10684 KB Output is correct
6 Correct 16 ms 10684 KB Output is correct
7 Correct 16 ms 10812 KB Output is correct
8 Correct 16 ms 10572 KB Output is correct
9 Correct 15 ms 10572 KB Output is correct
10 Correct 15 ms 10572 KB Output is correct
11 Correct 16 ms 10572 KB Output is correct
12 Correct 15 ms 10684 KB Output is correct
13 Incorrect 16 ms 10684 KB Output isn't correct
14 Halted 0 ms 0 KB -