#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define SZ(val) (int)val.size()
#define all(val) val.begin(), val.end()
const int maxn = 1e5 + 4;
int n, k, a[maxn], b[maxn], q[maxn], idx[maxn], node[maxn];
vector<int> vals, que[3 * maxn];
struct seg_tree {
vector<int> t;
seg_tree() {
t.resize(4 * maxn);
}
void update(int pos, int val, int v = 1, int l = 1, int r = maxn - 1) {
if (l == r) {
t[v] += val;
return;
}
int m = (l + r) / 2;
if (pos <= m) update(pos, val, 2 * v, l, m);
else update(pos, val, 2 * v + 1, m + 1, r);
t[v] = t[2 * v] + t[2 * v + 1];
}
int walk(int v = 1, int l = 1, int r = maxn - 1) {
if (l == r) return l;
int m = (l + r) / 2;
if (t[2 * v + 1]) return walk(2 * v + 1, m + 1, r);
return walk(2 * v, l, m);
}
} IT1;
struct persistent {
vector<int> t, L, R;
int num;
persistent() {
num = 0;
t.resize(1e7);
L.resize(1e7);
R.resize(1e7);
}
int update(int pos, int val, int v, int l = 1, int r = maxn - 1) {
if (pos < l || pos > r) return v;
if (l == r) {
t[++num] = t[v] + val;
return num;
}
int m = (l + r) / 2, cur = ++num;
L[cur] = update(pos, val, L[v], l, m);
R[cur] = update(pos, val, R[v], m + 1, r);
t[cur] = t[L[cur]] + t[R[cur]];
return cur;
}
int get(int l, int r, int v, int tl = 1, int tr = maxn - 1) {
if (tl > r || tr < l) return 0;
if (tl >= l && tr <= r) return t[v];
int m = (tl + tr) / 2;
return get(l, r, L[v], tl, m) + get(l, r, R[v], m + 1, tr);
}
} IT2;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i], idx[i] = i;
vals.pb(a[i]); vals.pb(b[i]);
}
for (int i = 1; i <= k; i++) {
cin >> q[i];
vals.pb(q[i]);
}
sort(all(vals));
vals.erase(unique(all(vals)), vals.end());
for (int i = 1; i <= n; i++) {
a[i] = lower_bound(all(vals), a[i]) - vals.begin() + 1;
b[i] = lower_bound(all(vals), b[i]) - vals.begin() + 1;
}
for (int i = k; i >= 1; i--) {
q[i] = lower_bound(all(vals), q[i]) - vals.begin() + 1;
que[q[i]].pb(i);
node[i] = IT2.update(q[i], 1, node[i + 1]);
}
sort(idx + 1, idx + 1 + n, [&](int i, int j) {
return min(a[i], b[i]) > min(a[j], b[j]);
});
// for (int i = 1; i <= n; i++)
// clog << a[i] << ' ' << b[i] << endl;
// for (int i = 1; i <= k; i++)
// clog << q[i] << endl;
int pos = SZ(vals);
long long res = 0;
for (int i = 1; i <= n; i++) {
int lo = min(a[i], b[i]), hi = max(a[i], b[i]);
while (pos > lo) {
for (int i : que[pos])
IT1.update(i, 1);
pos--;
}
int p = IT1.walk();
res += (IT2.get(hi, SZ(vals), node[p]) & 1 ? vals[lo - 1] : vals[hi - 1]);
}
cout << res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
127836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
127836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
127836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
