| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 112169 | kimjg1119 | Fortune Telling 2 (JOI14_fortune_telling2) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <cstdio>
#include <vector>
#include <utility>
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tp;
typedef long long ll;
typedef struct node {
int le, ri;
int val;
}node;
typedef struct SegmentTree {
vector<node> N;
int root, n;
int alloc() {
N.push_back({ -1,-1,0 });
return (int)N.size()-1;
}
SegmentTree(int _n) : n(_n) {
root = alloc();
}
void update(int nx, int st, int en, int idx, int val) {
if (st == en && idx == st) {
N[nx].val = max(N[nx].val, val);
return;
}
else if (idx < st || en < idx) return;
int mid = ((ll)st + (ll)en) / 2;
if (N[nx].le == -1) {
int t = alloc();
N[nx].le = t;
}
if (N[nx].ri == -1) {
int t = alloc();
N[nx].ri = t;
}
update(N[nx].le, st, mid, idx, val);
update(N[nx].ri, mid + 1, en, idx, val);
N[nx].val = max(N[N[nx].le].val, N[N[nx].ri].val);
}
void update(int idx, int val) {
return update(root, 0, n - 1, idx, val);
}
int query(int nx, int st, int en, int le, int ri) {
if (nx == -1) return 0;
if (le <= st && en <= ri) return N[nx].val;
else if (ri < st || en < le) return 0;
int mid = ((ll)st + (ll)en) / 2;
return max(query(N[nx].le, st, mid, le, ri), query(N[nx].ri, mid + 1, en, le, ri));
}
int query(int le, int ri) {
return query(root, 0, n - 1, le, ri);
}
}ST;
int tree[200005];
void update(int idx) {
for (int i = idx; i < 200005; i += (i&-i))
tree[i] += 1;
}
int query(int idx) {
int s = 0;
for (int i = idx; i > 0; i -= (i&-i))
s += tree[i];
return s;
}
int main() {
int n, k;
scanf("%d %d", &n, &k);
vector<pii> V, Q;
for (int i = 0; i < n; i++) {
int t1, t2;
scanf("%d %d", &t1, &t2);
V.emplace_back(t1, t2);
}
sort(V.begin(), V.end(), [&](pii a, pii b) {
return min(a.x, a.y) > min(b.x, b.y);
});
for (int i = 0; i < k; i++) {
int t;
scanf("%d", &t);
Q.emplace_back(t, i+1);
}
sort(Q.begin(), Q.end(), greater<pii>());
int last = 0;
ll ans = 0;
ST S(2 * 1e9 + 5);
for (int i = 0; i < V.size(); i++) {
int a = min(V[i].x, V[i].y), b = max(V[i].x, V[i].y);
while (last < Q.size()) {
if (Q[last].x >= a) {
S.update(Q[last].x, Q[last].y);
update(Q[last].y);
last++;
}
else break;
}
int bound = S.query(a, b - 1);
if (!bound) {
ans += a;
continue;
}
int ret = query(200000) - query(bound);
if (ret % 2) ans += a;
else ans += b;
}
printf("%lld", ans);
return 0;
}