#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
const int N = 2e5 + 7, C = 3 * N;
int n, k; int a[N], b[N], t[N], r[C], mx[C << 2];
void build(int v, int tl, int tr) {
if (tl == tr) { mx[v] = r[tl]; return; }
int tm = (tl + tr) >> 1;
build(v * 2 + 1, tl, tm); build(v * 2 + 2, tm + 1, tr);
mx[v] = max(mx[v * 2 + 1], mx[v * 2 + 2]);
}
int get(int v, int tl, int tr, int l, int r) {
if (tr < l || r < tl) return -1;
if (l <= tl && tr <= r) return mx[v];
int tm = (tl + tr) >> 1;
return max(get(v * 2 + 1, tl, tm, l, r), get(v * 2 + 2, tm + 1, tr, l, r));
}
vector <int> c;
int pos(int x) { return lower_bound(c.begin(), c.end(), x) - c.begin(); }
int last[N], d[N];
vector <int> card[N];
int f[C];
void upd(int i) { i = C - i - 1; for (; i < C; i |= i + 1) ++f[i]; }
int get(int i) { i = C - i - 1; int ans = 0; for (; i >= 0; i &= i + 1, --i) ans += f[i]; return ans; }
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
#else
ios_base::sync_with_stdio(0); cin.tie(0);
#endif
cin >> n >> k;
for (int i = 0; i < n; ++i) { cin >> a[i] >> b[i]; c.app(a[i]); c.app(b[i]); }
for (int i = 0; i < k; ++i) { cin >> t[i]; c.app(t[i]); }
sort(all(c)); c.resize(unique(all(c)) - c.begin());
for (int i = 0; i < n; ++i) { a[i] = pos(a[i]); b[i] = pos(b[i]); }
for (int i = 0; i < k; ++i) { t[i] = pos(t[i]); r[t[i]] = i; }
build(0, 0, C - 1);
for (int i = 0; i < n; ++i) {
last[i] = get(0, 0, C - 1, min(a[i], b[i]), max(a[i], b[i]) - 1);
card[last[i] + 1].app(i);
}
for (int i = k - 1; i >= 0; --i) {
upd(t[i]);
for (int c : card[i]) {
d[c] = get(max(a[c], b[c]));
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
if (a[i] < b[i] && last[i] == -1) ++d[i];
if (d[i] & 1) { ans += c[min(a[i], b[i])]; }
else { ans += c[max(a[i], b[i])]; }
}
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
21752 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
21552 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
21752 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
21552 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
21752 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
21552 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
