oj.uz

Submission #553730

# Submission time Handle Problem Language Result Execution time Memory
553730 2022-04-26T17:38:09 Z QwertyPi Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 3000 ms 216020 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+3;
int A[N], B[N], C[N];
int x1[N], x2[N], pa[N];
map<int, int> M; int m;

struct node{
	node *l, *r;
	int tl, tr, cnt;
	node(int L, int R, int cnt) : l(nullptr), r(nullptr), tl(L), tr(R), cnt(cnt){};
	~node(){};
};

void build(node*& t, int l, int r){
	t = new node(l, r, 0);
	if(l == r) return;
	int mid = (l + r) / 2;
	build(t->l, l, mid); 
	build(t->r, mid + 1, r);
}

node* upd(node* t, int tl, int tr, int q, int delta){
	if(tl == tr){
		node* ret = new node(tl, tr, (t ? t->cnt : 0) + delta);
		return ret;
	}
	int tm = (tl + tr) / 2;
	node* ret = new node(tl, tr, t->cnt);
	ret->l = t->l, ret->r = t->r;
	if(q <= tm){
		ret->l = upd(t->l, tl, tm, q, delta);
	}else{
		ret->r = upd(t->r, tm + 1, tr, q, delta);
	}
	ret->cnt = (ret->l ? ret->l->cnt : 0) + (ret->r ? ret->r->cnt : 0);
	return ret;
}

int qry(node* t, int r){
	if(t->tl == t->tr) return t->cnt;
	if(r <= t->l->tr) return qry(t->l, r);
	else return t->l->cnt + qry(t->r, r);
}

int qry(node* t, int l, int r){
	return qry(t, r) - qry(t, l - 1);
}

node* T[N];

int32_t main(){
	int n, k;
	cin >> n >> k;
	for(int i = 0; i < n; i++){
		cin >> A[i] >> B[i];
		x1[i] = min(A[i], B[i]);
		x2[i] = max(A[i], B[i]);
		pa[i] = x1[i] != A[i];
	}
	for(int i = 1; i <= k; i++){
		cin >> C[i];
	}
	{
		vector<int> v; for(int i = 1; i <= k; i++) v.push_back(C[i]);
		sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end()) - v.begin());
		int idx = 0; for(auto i : v) M[i] = ++idx; M[1 << 30] = ++idx; m = idx;
		for(int i = 1; i <= k; i++) C[i] = M[C[i]];
	}
	
	build(T[0], 0, m);
	for(int i = 1; i <= k; i++){
		T[i] = upd(T[i - 1], 0, m, C[i], 1);
	}
	long long ans = 0;
	for(int i = 0; i < n; i++){
		int y1 = M.lower_bound(x1[i])->second;
		int y2 = M.lower_bound(x2[i])->second;
		int l = 0, r = k, tot = qry(T[k], y1, y2 - 1);
		while(l != r){
			int mid = (l + r + 1) / 2;
			if(qry(T[mid], y1, y2 - 1) == tot){
				r = mid - 1;
			}else{
				l = mid;
			}
		}
		if(l != 0) pa[i] = true;
		int cnt = qry(T[k], y2, m) - qry(T[l], y2, m);
		pa[i] ^= cnt % 2;
		ans += pa[i] ? x2[i] : x1[i];
	}
	cout << ans << endl;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 992 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 5 ms 1024 KB Output is correct
4 Correct 4 ms 984 KB Output is correct
5 Correct 4 ms 980 KB Output is correct
6 Correct 4 ms 980 KB Output is correct
7 Correct 5 ms 980 KB Output is correct
8 Correct 4 ms 980 KB Output is correct
9 Correct 3 ms 980 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 3 ms 976 KB Output is correct
13 Correct 4 ms 980 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 992 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 5 ms 1024 KB Output is correct
4 Correct 4 ms 984 KB Output is correct
5 Correct 4 ms 980 KB Output is correct
6 Correct 4 ms 980 KB Output is correct
7 Correct 5 ms 980 KB Output is correct
8 Correct 4 ms 980 KB Output is correct
9 Correct 3 ms 980 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 3 ms 976 KB Output is correct
13 Correct 4 ms 980 KB Output is correct
14 Correct 57 ms 9044 KB Output is correct
15 Correct 128 ms 18776 KB Output is correct
16 Correct 229 ms 28768 KB Output is correct
17 Correct 390 ms 39108 KB Output is correct
18 Correct 346 ms 39068 KB Output is correct
19 Correct 359 ms 39056 KB Output is correct
20 Correct 328 ms 39108 KB Output is correct
21 Correct 329 ms 39084 KB Output is correct
22 Correct 163 ms 36700 KB Output is correct
23 Correct 162 ms 36220 KB Output is correct
24 Correct 181 ms 35564 KB Output is correct
25 Correct 173 ms 37304 KB Output is correct
26 Correct 204 ms 38768 KB Output is correct
27 Correct 314 ms 39016 KB Output is correct
28 Correct 231 ms 39224 KB Output is correct
29 Correct 383 ms 39100 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 992 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 5 ms 1024 KB Output is correct
4 Correct 4 ms 984 KB Output is correct
5 Correct 4 ms 980 KB Output is correct
6 Correct 4 ms 980 KB Output is correct
7 Correct 5 ms 980 KB Output is correct
8 Correct 4 ms 980 KB Output is correct
9 Correct 3 ms 980 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 3 ms 976 KB Output is correct
13 Correct 4 ms 980 KB Output is correct
14 Correct 57 ms 9044 KB Output is correct
15 Correct 128 ms 18776 KB Output is correct
16 Correct 229 ms 28768 KB Output is correct
17 Correct 390 ms 39108 KB Output is correct
18 Correct 346 ms 39068 KB Output is correct
19 Correct 359 ms 39056 KB Output is correct
20 Correct 328 ms 39108 KB Output is correct
21 Correct 329 ms 39084 KB Output is correct
22 Correct 163 ms 36700 KB Output is correct
23 Correct 162 ms 36220 KB Output is correct
24 Correct 181 ms 35564 KB Output is correct
25 Correct 173 ms 37304 KB Output is correct
26 Correct 204 ms 38768 KB Output is correct
27 Correct 314 ms 39016 KB Output is correct
28 Correct 231 ms 39224 KB Output is correct
29 Correct 383 ms 39100 KB Output is correct
30 Correct 630 ms 208684 KB Output is correct
31 Correct 1144 ms 210260 KB Output is correct
32 Correct 1733 ms 212200 KB Output is correct
33 Execution timed out 3081 ms 216020 KB Time limit exceeded
34 Halted 0 ms 0 KB -