#include <bits/stdc++.h>
using namespace std;
struct treemax {
typedef int T;
T f(T a, T b) { return max(a, b); }
vector<T> s;
int n;
T unit = 0;
treemax(int nn, T fil) : s(2 * nn, fil), n(nn), unit(fil) {}
void update(int p, T v)
{
p += n;
for(s[p] = f(s[p], v); p /= 2;) {
s[p] = f(s[2 * p], s[2 * p + 1]);
}
}
T query(int a, int b)
{
T ra = unit, rb = unit;
for(a += n, b += n + 1; a < b; a /= 2, b /= 2) {
if(a % 2) ra = f(ra, s[a++]);
if(b % 2) rb = f(rb, s[--b]);
}
return f(ra, rb);
}
};
struct treesum {
typedef int T;
T f(T a, T b) { return a + b; }
vector<T> s;
int n;
T unit = 0;
treesum(int nn, T fil) : s(2 * nn, fil), n(nn), unit(fil) {}
void update(int p, T v)
{
p += n;
for(s[p] = f(s[p], v); p /= 2;) {
s[p] = f(s[2 * p], s[2 * p + 1]);
}
}
T query(int a, int b)
{
T ra = unit, rb = unit;
for(a += n, b += n + 1; a < b; a /= 2, b /= 2) {
if(a % 2) ra = f(ra, s[a++]);
if(b % 2) rb = f(rb, s[--b]);
}
return f(ra, rb);
}
};
#define make_unique(v) sort((v).begin(), (v).end()), (v).erase(unique((v).begin(), (v).end()), (v).end())
struct scaler {
vector<int> all;
void insert(int x) { all.emplace_back(x); }
void init() { make_unique(all); }
int get(int x) { return lower_bound(all.begin(), all.end(), x) - all.begin(); }
};
int32_t main()
{
cin.tie(0)->sync_with_stdio(0);
int n, q;
cin >> n >> q;
vector<int> flip(n + 1);
vector<int> a(n + 1), b(n + 1), c(q + 1);
scaler s;
for(int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
if(a[i] > b[i]) {
swap(a[i], b[i]);
flip[i] = 1;
}
s.insert(a[i]), s.insert(b[i]);
}
vector<int> ra = a, rb = b;
for(int i = 1; i <= q; i++) {
cin >> c[i];
s.insert(c[i]);
}
s.insert(-1);
s.init();
int szz = (int)s.all.size();
treemax rmq(szz + 100, 0);
for(int i = 1; i <= q; i++) {
c[i] = s.get(c[i]);
rmq.update(c[i], i);
}
vector<pair<int, int>> intervals;
for(int i = 1; i <= n; i++) {
a[i] = s.get(a[i]), b[i] = s.get(b[i]);
int when = rmq.query(a[i], b[i] - 1);
if(when != 0) {
flip[i] = 1;
}
intervals.emplace_back(when + 1, i);
}
sort(intervals.begin(), intervals.end());
treesum sum(szz + 100, 0);
int ptr = q;
for(int i = n - 1; i >= 0; i--) {
while(ptr >= intervals[i].first) {
sum.update(c[ptr], 1);
ptr--;
}
flip[i] ^= (sum.query(b[i], szz + 50) % 2);
}
long long ans = 0;
for(int i = 1; i <= n; ++i) {
if(!flip[i]) {
ans += ra[i];
}
else {
ans += rb[i];
}
}
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
