oj.uz

Submission #399844

# Submission time Handle Problem Language Result Execution time Memory
399844 2021-05-06T17:52:57 Z nikatamliani Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 539 ms 55452 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10, MAX = 0, SUM = 1;
int tree[4*N], a[N], b[N], t[N], save_a[N], save_b[N];
int n, k;
long long sum;
vector<int> q[N];
void maxi(int &x, int y) {
	if(x < y) x = y;
}
void update(int l, int r, int x, int val, int p, int type) {
	if(l > x || r < x) return;
	if(l == r) {
		if(type == MAX) {
			maxi(tree[p], val);
		} else if(type == SUM) {
			tree[p] += val;
		} else {
			assert(false);
		}
	} else {
		int m = l + r >> 1;
		update(l, m, x, val, p << 1, type);
		update(m+1, r, x, val, p << 1 | 1, type);
		if(type == MAX) {
			tree[p] = max(tree[p << 1], tree[p << 1 | 1]);
		} else if(type == SUM) {
			tree[p] = tree[p << 1] + tree[p << 1 | 1];
		} else {
			assert(false);
		}
	}
}
int query(int l, int r, int L, int R, int p, int type) { 
	if(l > R || L > r) return 0;
	if(L <= l && R >= r) {
		return tree[p];
	}
	int m = l + r >> 1;
	int lft = query(l, m, L, R, p << 1, type);
	int rgh = query(m+1, r, L, R, p << 1 | 1, type);
	if(type == MAX) {
		return max(lft, rgh);
	} else if(type == SUM) {
		return lft+rgh;
	} else {
		assert(false);
	}
}
void update(int x, int val, int type) {
	update(1, N-1, x, val, 1, type);
}
int query(int l, int r, int type) {
	return query(1, N-1, l, r, 1, type);
}
void compress(vector<int*> &coords) {
	int cnt = 0, prv = -1;
	sort(coords.begin(), coords.end(), [](int* x, int *y) {
		return *x < *y;
	});
	for(int i = 0; i < (int)coords.size(); ++i) {
		if(prv < *coords[i]) ++cnt;
		prv = *coords[i];
		*coords[i] = cnt;
	}
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i] >> b[i];
		if(a[i] == b[i]) {
			sum += a[i];
			--i;
			--n;
		}
	}
	if(n == 0) {
		cout << sum << endl;
		return 0;
	}
	vector<int*> coords;
	for(int i = 1; i <= k; ++i) {
		cin >> t[i];
		coords.push_back(&t[i]);
	}
	for(int i = 1; i <= n; ++i) {
		save_a[i] = a[i];
		save_b[i] = b[i];
		coords.push_back(&a[i]);
		coords.push_back(&b[i]);
	}
	compress(coords);
	for(int i = 1; i <= k; ++i) {
		update(t[i], i, MAX);
	}
	for(int i = 1; i <= n; ++i) {
		int r = query(min(a[i], b[i]), max(a[i], b[i])-1, MAX);
		q[r].push_back(i);
	}
	memset(tree, 0, sizeof tree);
	for(int r = k; r >= 0; --r) {
		for(int i : q[r]) {
			int parity = query(max(a[i], b[i]), N-1, SUM) % 2;
			if(r > 0) {
				parity ^= a[i] < b[i];
			}
			sum += parity ? save_b[i] : save_a[i];
		}
		update(t[r], 1, SUM);
	}
	cout << sum << endl;
}

Compilation message

fortune_telling2.cpp: In function 'void update(int, int, int, int, int, int)':
fortune_telling2.cpp:22:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |   int m = l + r >> 1;
      |           ~~^~~
fortune_telling2.cpp: In function 'int query(int, int, int, int, int, int)':
fortune_telling2.cpp:39:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |  int m = l + r >> 1;
      |          ~~^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 39500 KB Output is correct
2 Correct 23 ms 39524 KB Output is correct
3 Correct 24 ms 39536 KB Output is correct
4 Correct 25 ms 39496 KB Output is correct
5 Correct 27 ms 39500 KB Output is correct
6 Correct 24 ms 39500 KB Output is correct
7 Correct 23 ms 39500 KB Output is correct
8 Correct 24 ms 39568 KB Output is correct
9 Correct 23 ms 39480 KB Output is correct
10 Correct 23 ms 39540 KB Output is correct
11 Correct 24 ms 39500 KB Output is correct
12 Correct 24 ms 39500 KB Output is correct
13 Correct 23 ms 39500 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 39500 KB Output is correct
2 Correct 23 ms 39524 KB Output is correct
3 Correct 24 ms 39536 KB Output is correct
4 Correct 25 ms 39496 KB Output is correct
5 Correct 27 ms 39500 KB Output is correct
6 Correct 24 ms 39500 KB Output is correct
7 Correct 23 ms 39500 KB Output is correct
8 Correct 24 ms 39568 KB Output is correct
9 Correct 23 ms 39480 KB Output is correct
10 Correct 23 ms 39540 KB Output is correct
11 Correct 24 ms 39500 KB Output is correct
12 Correct 24 ms 39500 KB Output is correct
13 Correct 23 ms 39500 KB Output is correct
14 Correct 43 ms 40052 KB Output is correct
15 Correct 65 ms 40452 KB Output is correct
16 Correct 85 ms 40880 KB Output is correct
17 Correct 107 ms 41408 KB Output is correct
18 Correct 108 ms 41412 KB Output is correct
19 Correct 107 ms 41360 KB Output is correct
20 Correct 113 ms 41456 KB Output is correct
21 Correct 126 ms 41608 KB Output is correct
22 Correct 96 ms 41388 KB Output is correct
23 Correct 95 ms 41408 KB Output is correct
24 Correct 94 ms 41568 KB Output is correct
25 Correct 96 ms 41616 KB Output is correct
26 Correct 90 ms 41264 KB Output is correct
27 Correct 102 ms 41400 KB Output is correct
28 Correct 105 ms 41412 KB Output is correct
29 Correct 100 ms 41500 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 39500 KB Output is correct
2 Correct 23 ms 39524 KB Output is correct
3 Correct 24 ms 39536 KB Output is correct
4 Correct 25 ms 39496 KB Output is correct
5 Correct 27 ms 39500 KB Output is correct
6 Correct 24 ms 39500 KB Output is correct
7 Correct 23 ms 39500 KB Output is correct
8 Correct 24 ms 39568 KB Output is correct
9 Correct 23 ms 39480 KB Output is correct
10 Correct 23 ms 39540 KB Output is correct
11 Correct 24 ms 39500 KB Output is correct
12 Correct 24 ms 39500 KB Output is correct
13 Correct 23 ms 39500 KB Output is correct
14 Correct 43 ms 40052 KB Output is correct
15 Correct 65 ms 40452 KB Output is correct
16 Correct 85 ms 40880 KB Output is correct
17 Correct 107 ms 41408 KB Output is correct
18 Correct 108 ms 41412 KB Output is correct
19 Correct 107 ms 41360 KB Output is correct
20 Correct 113 ms 41456 KB Output is correct
21 Correct 126 ms 41608 KB Output is correct
22 Correct 96 ms 41388 KB Output is correct
23 Correct 95 ms 41408 KB Output is correct
24 Correct 94 ms 41568 KB Output is correct
25 Correct 96 ms 41616 KB Output is correct
26 Correct 90 ms 41264 KB Output is correct
27 Correct 102 ms 41400 KB Output is correct
28 Correct 105 ms 41412 KB Output is correct
29 Correct 100 ms 41500 KB Output is correct
30 Correct 214 ms 42172 KB Output is correct
31 Correct 283 ms 43624 KB Output is correct
32 Correct 356 ms 45492 KB Output is correct
33 Correct 511 ms 49320 KB Output is correct
34 Correct 200 ms 43916 KB Output is correct
35 Correct 513 ms 55176 KB Output is correct
36 Correct 516 ms 55012 KB Output is correct
37 Correct 539 ms 55076 KB Output is correct
38 Correct 522 ms 55032 KB Output is correct
39 Correct 505 ms 54948 KB Output is correct
40 Correct 503 ms 55452 KB Output is correct
41 Correct 511 ms 55008 KB Output is correct
42 Correct 503 ms 54908 KB Output is correct
43 Correct 440 ms 55132 KB Output is correct
44 Correct 457 ms 55052 KB Output is correct
45 Correct 427 ms 54880 KB Output is correct
46 Correct 416 ms 53224 KB Output is correct
47 Correct 392 ms 52876 KB Output is correct
48 Correct 440 ms 55104 KB Output is correct
49 Correct 429 ms 55296 KB Output is correct