#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;
bool is_flipped[N];
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]) {
is_flipped[i] = query(max(a[i], b[i]), N-1, SUM) % 2;
}
update(t[r], 1, SUM);
}
for(int i = 1; i <= n; ++i) {
if(is_flipped[i]) {
sum += save_b[i];
} else {
sum += save_a[i];
}
}
cout << sum << endl;
}
Compilation message
fortune_telling2.cpp: In function 'void update(int, int, int, int, int, int)':
fortune_telling2.cpp:23:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | int m = l + r >> 1;
| ~~^~~
fortune_telling2.cpp: In function 'int query(int, int, int, int, int, int)':
fortune_telling2.cpp:40:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
40 | int m = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
