#include <bits/stdc++.h>
using namespace std;
int a[200005], b[200005], c[200005], res[200005], t[2400005], tt[2400005], dd[200005], z = 0;
map<int, int> m;
vector<pair<int, int>> g[200005];
void update(int v, int tl, int tr, int x, int y) {
if (tl == tr) {
t[v] = max(t[v], y);
return;
}
int mid = (tl + tr) / 2;
if (mid >= x) update(v * 2, tl, mid, x, y);
else update(v * 2 + 1, mid + 1, tr, x, y);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
int sum(int v, int tl, int tr, int l, int r) {
if (l > r) return 0;
if (tl == l && tr == r) {
return t[v];
}
int mid = (tl + tr) / 2;
return max(sum(v * 2, tl, mid, l, min(r, mid)), sum(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r));
}
void update2(int v, int tl, int tr, int x) {
if (tl == tr) {
tt[v]++;
return;
}
int mid = (tl + tr) / 2;
if (mid >= x) update2(v * 2, tl, mid, x);
else update2(v * 2 + 1, mid + 1, tr, x);
tt[v] = tt[v * 2] + tt[v * 2 + 1];
}
int sum2(int v, int tl, int tr, int l, int r) {
if (l > r) return 0;
if (tl == l && tr == r) {
return tt[v];
}
int mid = (tl + tr) / 2;
return sum2(v * 2, tl, mid, l, min(r, mid)) + sum2(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
vector<int> v;
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
v.push_back(a[i]);
v.push_back(b[i]);
}
for (int i = 1; i <= q; i++) {
cin >> c[i];
v.push_back(c[i]);
}
sort(v.begin(), v.end());
for (int w : v) {
if (!m.count(w)) {
m[w] = ++z;
dd[z] = w;
}
}
for (int i = 1; i <= n; i++) a[i] = m[a[i]], b[i] = m[b[i]];
for (int i = 1; i <= q; i++) {
c[i] = m[c[i]];
update(1, 1, z, c[i], i);
}
for (int i = 1; i <= n; i++) {
if (a[i] == b[i]) res[i] = 1;
else {
if (a[i] < b[i]) {
res[i] = 1;
swap(a[i], b[i]);
}
int h = sum(1, 1, z, b[i], a[i] - 1) + 1;
g[h].push_back({i, a[i]});
}
}
for (int i = q; i >= 1; i--) {
update2(1, 1, z, c[i]);
for (auto w : g[i]) {
int h = sum2(1, 1, z, w.second, z);
if (h & 1) res[w.first] ^= 1;
}
}
long long int d = 0;
for (int i = 1; i <= n; i++) {
if (res[i] == 0) d += dd[a[i]];
else d += dd[b[i]];
}
cout << d;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
