#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <cstdio>
#include <vector>
#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;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:93:27: error: 'greater' was not declared in this scope
sort(Q.begin(), Q.end(), greater<pii>());
^~~~~~~
fortune_telling2.cpp:93:38: error: expected primary-expression before '>' token
sort(Q.begin(), Q.end(), greater<pii>());
^
fortune_telling2.cpp:93:40: error: expected primary-expression before ')' token
sort(Q.begin(), Q.end(), greater<pii>());
^
fortune_telling2.cpp:98:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < V.size(); i++) {
~~^~~~~~~~~~
fortune_telling2.cpp:100:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (last < Q.size()) {
~~~~~^~~~~~~~~~
fortune_telling2.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &k);
~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &t1, &t2);
~~~~~^~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &t);
~~~~~^~~~~~~~~~
