oj.uz

Submission #399841

# Submission time Handle Problem Language Result Execution time Memory
399841 2021-05-06T17:51:36 Z nikatamliani Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 434 ms 35524 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+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 13 ms 19916 KB Output is correct
2 Correct 13 ms 19988 KB Output is correct
3 Correct 13 ms 20020 KB Output is correct
4 Correct 14 ms 20032 KB Output is correct
5 Correct 14 ms 20044 KB Output is correct
6 Correct 14 ms 19980 KB Output is correct
7 Correct 14 ms 19972 KB Output is correct
8 Correct 14 ms 20004 KB Output is correct
9 Correct 14 ms 20044 KB Output is correct
10 Correct 14 ms 19916 KB Output is correct
11 Correct 14 ms 20044 KB Output is correct
12 Correct 14 ms 20044 KB Output is correct
13 Correct 14 ms 20044 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19916 KB Output is correct
2 Correct 13 ms 19988 KB Output is correct
3 Correct 13 ms 20020 KB Output is correct
4 Correct 14 ms 20032 KB Output is correct
5 Correct 14 ms 20044 KB Output is correct
6 Correct 14 ms 19980 KB Output is correct
7 Correct 14 ms 19972 KB Output is correct
8 Correct 14 ms 20004 KB Output is correct
9 Correct 14 ms 20044 KB Output is correct
10 Correct 14 ms 19916 KB Output is correct
11 Correct 14 ms 20044 KB Output is correct
12 Correct 14 ms 20044 KB Output is correct
13 Correct 14 ms 20044 KB Output is correct
14 Correct 31 ms 20792 KB Output is correct
15 Correct 68 ms 21516 KB Output is correct
16 Correct 77 ms 22320 KB Output is correct
17 Correct 104 ms 23068 KB Output is correct
18 Correct 96 ms 22988 KB Output is correct
19 Correct 95 ms 23068 KB Output is correct
20 Correct 114 ms 23164 KB Output is correct
21 Correct 95 ms 23156 KB Output is correct
22 Correct 84 ms 22520 KB Output is correct
23 Correct 84 ms 22516 KB Output is correct
24 Correct 84 ms 22588 KB Output is correct
25 Correct 87 ms 22784 KB Output is correct
26 Correct 79 ms 22592 KB Output is correct
27 Correct 89 ms 23000 KB Output is correct
28 Correct 85 ms 23084 KB Output is correct
29 Correct 90 ms 23156 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19916 KB Output is correct
2 Correct 13 ms 19988 KB Output is correct
3 Correct 13 ms 20020 KB Output is correct
4 Correct 14 ms 20032 KB Output is correct
5 Correct 14 ms 20044 KB Output is correct
6 Correct 14 ms 19980 KB Output is correct
7 Correct 14 ms 19972 KB Output is correct
8 Correct 14 ms 20004 KB Output is correct
9 Correct 14 ms 20044 KB Output is correct
10 Correct 14 ms 19916 KB Output is correct
11 Correct 14 ms 20044 KB Output is correct
12 Correct 14 ms 20044 KB Output is correct
13 Correct 14 ms 20044 KB Output is correct
14 Correct 31 ms 20792 KB Output is correct
15 Correct 68 ms 21516 KB Output is correct
16 Correct 77 ms 22320 KB Output is correct
17 Correct 104 ms 23068 KB Output is correct
18 Correct 96 ms 22988 KB Output is correct
19 Correct 95 ms 23068 KB Output is correct
20 Correct 114 ms 23164 KB Output is correct
21 Correct 95 ms 23156 KB Output is correct
22 Correct 84 ms 22520 KB Output is correct
23 Correct 84 ms 22516 KB Output is correct
24 Correct 84 ms 22588 KB Output is correct
25 Correct 87 ms 22784 KB Output is correct
26 Correct 79 ms 22592 KB Output is correct
27 Correct 89 ms 23000 KB Output is correct
28 Correct 85 ms 23084 KB Output is correct
29 Correct 90 ms 23156 KB Output is correct
30 Correct 215 ms 24948 KB Output is correct
31 Correct 298 ms 27092 KB Output is correct
32 Correct 326 ms 29852 KB Output is correct
33 Incorrect 434 ms 35524 KB Output isn't correct
34 Halted 0 ms 0 KB -