oj.uz

답안 #242339

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
242339 2020-06-27T08:59:07 Z super_j6 수확 (JOI20_harvest) C++14
0 / 100
 258 ms 36956 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;
ll a[mxn], b[mxn];
ll rt[mxn], vis[mxn], p[mxn], d[mxn], l[mxn], r[mxn];
vector<pii> qry[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;
	
	for(int i = 0; i < q; i++){
		ll x, y;
		cin >> x >> y;
		x--;
		qry[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;
		qry[rt[x]].push_back({d[x] + (k + b[i] - a[x]) % k, {-1, x}});
	}
	
	for(int i = 0; i < n; i++){
		if(rt[i] != i) continue;
		tre.clr();
		sort(qry[i].begin(), qry[i].end());
		
		ll len = d[p[i]] + dst(p[i], i);
		for(pii &j : qry[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(qry[i].begin(), qry[i].end());
		
		ll dt = 0;
		for(pii j : qry[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

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 10112 KB Output is correct
2 Correct 13 ms 10368 KB Output is correct
3 Correct 18 ms 10620 KB Output is correct
4 Correct 16 ms 10624 KB Output is correct
5 Correct 16 ms 10748 KB Output is correct
6 Correct 16 ms 10748 KB Output is correct
7 Correct 16 ms 10748 KB Output is correct
8 Correct 15 ms 10496 KB Output is correct
9 Correct 15 ms 10496 KB Output is correct
10 Correct 15 ms 10496 KB Output is correct
11 Correct 15 ms 10496 KB Output is correct
12 Correct 15 ms 10748 KB Output is correct
13 Incorrect 17 ms 10748 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 186 ms 22528 KB Output is correct
2 Incorrect 258 ms 36956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 10112 KB Output is correct
2 Correct 13 ms 10368 KB Output is correct
3 Correct 18 ms 10620 KB Output is correct
4 Correct 16 ms 10624 KB Output is correct
5 Correct 16 ms 10748 KB Output is correct
6 Correct 16 ms 10748 KB Output is correct
7 Correct 16 ms 10748 KB Output is correct
8 Correct 15 ms 10496 KB Output is correct
9 Correct 15 ms 10496 KB Output is correct
10 Correct 15 ms 10496 KB Output is correct
11 Correct 15 ms 10496 KB Output is correct
12 Correct 15 ms 10748 KB Output is correct
13 Incorrect 17 ms 10748 KB Output isn't correct
14 Halted 0 ms 0 KB -