oj.uz

Submission #30871

# Submission time Handle Problem Language Result Execution time Memory
30871 2017-07-29T14:45:36 Z Navick Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 603 ms 20928 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 2e5 + 10, LOG = 20;

int n, k, a[N], b[N];
pii t[N];

int seg[LOG][N];


void build(int lg = 0, int s = 0, int e = k){
	if(e - s < 2){
		seg[lg][s] = t[s].S;
		return ;
	}
	int mid = (s + e)/2;
	build(lg + 1, s , mid);
	build(lg + 1, mid , e);
	merge(seg[lg + 1] + s, seg[lg + 1] + mid, seg[lg + 1] + mid, seg[lg + 1] + e, seg[lg] + s);
}

int get_max(int lg ,int L, int R, int s = 0, int e = k){
	if(L<=s && e<=R){
		return seg[lg][e - 1];
	}
	if(L>=e || s>=R)return -1;
	int mid = (s + e)/2;
	return max(get_max(lg + 1, L, R, s, mid), get_max(lg + 1, L, R, mid, e));
}

int get_cnt(int lg, int vl, int L, int R, int s = 0, int e = k){
	if(L<=s && e<=R){
		return (e - s) - (upper_bound(seg[lg] + s, seg[lg] + e, vl) - (seg[lg] + s));
	}
	if(L>=e || s>=R)return 0;
	int mid = (s + e)/2;
	return get_cnt(lg + 1, vl, L, R, s, mid) + get_cnt(lg + 1, vl, L, R, mid, e);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	for(int i=0; i<n; i++)
		cin >> a[i] >> b[i];

	for(int i=0; i<k; i++){
		cin >> t[i].F; t[i].S = i;
	}

	sort(t, t + k);

	build();

	ll sum = 0;

	for(int i=0; i<n; i++){
		bool turn;
		if(a[i] < b[i])turn = true;
		else turn = false;
		int lo = lower_bound(t, t + k, pii(min(a[i], b[i]), -1)) - t;
		int hi = lower_bound(t, t + k, pii(max(a[i], b[i]), -1)) - t;
		int tim = get_max(0, lo, hi);
		int xk = get_cnt(0, tim , hi, k);
		int delta = 0;
		if(turn){
			if(tim == -1)delta = xk;
			else delta = xk + 1;
		}else
			delta = xk;
		if(delta % 2 == 1)swap(a[i], b[i]);
		sum += a[i];
	}

	cout << sum << endl;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 20928 KB Output is correct
2 Correct 0 ms 20928 KB Output is correct
3 Correct 0 ms 20928 KB Output is correct
4 Correct 0 ms 20928 KB Output is correct
5 Correct 0 ms 20928 KB Output is correct
6 Correct 0 ms 20928 KB Output is correct
7 Correct 0 ms 20928 KB Output is correct
8 Correct 0 ms 20928 KB Output is correct
9 Correct 0 ms 20928 KB Output is correct
10 Correct 0 ms 20928 KB Output is correct
11 Correct 0 ms 20928 KB Output is correct
12 Correct 0 ms 20928 KB Output is correct
13 Correct 0 ms 20928 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20928 KB Output is correct
2 Correct 29 ms 20928 KB Output is correct
3 Correct 46 ms 20928 KB Output is correct
4 Correct 59 ms 20928 KB Output is correct
5 Correct 56 ms 20928 KB Output is correct
6 Correct 59 ms 20928 KB Output is correct
7 Correct 66 ms 20928 KB Output is correct
8 Correct 56 ms 20928 KB Output is correct
9 Correct 39 ms 20928 KB Output is correct
10 Correct 36 ms 20928 KB Output is correct
11 Correct 43 ms 20928 KB Output is correct
12 Correct 39 ms 20928 KB Output is correct
13 Correct 49 ms 20928 KB Output is correct
14 Correct 59 ms 20928 KB Output is correct
15 Correct 53 ms 20928 KB Output is correct
16 Correct 59 ms 20928 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 20928 KB Output is correct
2 Correct 176 ms 20928 KB Output is correct
3 Correct 266 ms 20928 KB Output is correct
4 Correct 603 ms 20928 KB Output is correct
5 Correct 63 ms 20928 KB Output is correct
6 Correct 559 ms 20928 KB Output is correct
7 Correct 563 ms 20928 KB Output is correct
8 Correct 533 ms 20928 KB Output is correct
9 Correct 483 ms 20928 KB Output is correct
10 Correct 506 ms 20928 KB Output is correct
11 Correct 353 ms 20928 KB Output is correct
12 Correct 489 ms 20928 KB Output is correct
13 Correct 533 ms 20928 KB Output is correct
14 Correct 253 ms 20928 KB Output is correct
15 Correct 213 ms 20928 KB Output is correct
16 Correct 213 ms 20928 KB Output is correct
17 Correct 283 ms 20928 KB Output is correct
18 Correct 246 ms 20928 KB Output is correct
19 Correct 479 ms 20928 KB Output is correct
20 Correct 376 ms 20928 KB Output is correct