oj.uz

Submission #242346

# Submission time Handle Problem Language Result Execution time Memory
242346 2020-06-27T09:12:39 Z super_j6 Harvest (JOI20_harvest) C++14
0 / 100
 262 ms 32216 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>
using namespace std;
#define endl '\n'
#define ll int64_t
#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[p[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 13 ms 9984 KB Output is correct
2 Correct 14 ms 10240 KB Output is correct
3 Correct 16 ms 10608 KB Output is correct
4 Correct 16 ms 10560 KB Output is correct
5 Correct 16 ms 10684 KB Output is correct
6 Correct 17 ms 10684 KB Output is correct
7 Correct 17 ms 10684 KB Output is correct
8 Correct 17 ms 10572 KB Output is correct
9 Correct 15 ms 10444 KB Output is correct
10 Correct 16 ms 10572 KB Output is correct
11 Correct 16 ms 10572 KB Output is correct
12 Correct 16 ms 10684 KB Output is correct
13 Correct 17 ms 10684 KB Output is correct
14 Incorrect 17 ms 10496 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 20096 KB Output is correct
2 Incorrect 262 ms 32216 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

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