#include <bits/stdc++.h>
using namespace std;
// trei tipuri: None/ Set = 1/ Toggle
const int nmax = 2e5 + 5;
vector<int> t;
int n, k;
namespace MTree {
vector<int> aint[nmax * 4];
vector<int> a, b;
void construct(int node = 1, int cl = 0, int cr = k - 1) {
if(cl == cr) {
aint[node].push_back(t[cl]);
return;
}
int mid = cl + cr >> 1;
construct(2 * node, cl, mid);
construct(2 * node + 1, mid + 1, cr);
a = aint[node * 2];
b = aint[node * 2 + 1];
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
while(!a.empty()) {
if(a.back() > b.back())
swap(a, b);
aint[node].push_back(a.back());
a.pop_back();
}
while(!b.empty())
aint[node].push_back(b.back()), b.pop_back();
}
int query(int poz, int val, int node = 1, int cl = 0, int cr = k - 1) {
if(cr < poz)
return 0;
if(poz <= cl)
return distance(lower_bound(aint[node].begin(), aint[node].end(), val), aint[node].end()) & 1;
int mid = cl + cr >> 1;
return query(poz, val, 2 * node, cl, mid) ^ query(poz, val, 2 * node + 1, mid + 1, cr);
}
int descend(int l, int r, int node = 1, int cl = 0, int cr = k - 1) {
if(lower_bound(aint[node].begin(), aint[node].end(), l) == upper_bound(aint[node].begin(), aint[node].end(), r))
return cl - 1;
if(cl == cr)
return cl;
int mid = cl + cr >> 1, temp = descend(l, r, 2 * node + 1, mid + 1, cr);
if(temp == mid)
return descend(l, r, 2 * node, cl, mid);
return temp;
}
};
int a[nmax], b[nmax];
int main() {
cin >> n >> k;
for(int i = 0; i < n; i++)
cin >> a[i] >> b[i];
t.resize(k);
for(auto &x : t)
cin >> x;
MTree::construct();
int sum = 0;
for(int i = 0; i < n; i++) {
int start = a[i] > b[i];
if(start)
swap(a[i], b[i]);
int u = MTree::descend(a[i], b[i] - 1);
if(u != -1)
start = 1;
start ^= MTree::query(u + 1, b[i]);
sum += (start ? b[i] : a[i]);
}
cout << sum << '\n';
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'void MTree::construct(int, int, int)':
fortune_telling2.cpp:19:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
19 | int mid = cl + cr >> 1;
| ~~~^~~~
fortune_telling2.cpp: In function 'int MTree::query(int, int, int, int, int)':
fortune_telling2.cpp:40:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
40 | int mid = cl + cr >> 1;
| ~~~^~~~
fortune_telling2.cpp: In function 'int MTree::descend(int, int, int, int, int)':
fortune_telling2.cpp:48:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
48 | int mid = cl + cr >> 1, temp = descend(l, r, 2 * node + 1, mid + 1, cr);
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
