#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
#define mkp make_pair
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define eb emplace_back
#define F first
#define S second
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
const ll ool = 1e18 + 9;
const int N = 6e5 + 6, C = 21, oo = 1e9 + 9;
int n, Q, a[N], b[N], c[N], vala[N], valb[N], t[N], mx[C][N], lg[N];
bool flip[N];
ll ans;
vector < int > g[N], qr[N];
vector < pair < int, int > > vec;
void upd(int i) {
for (; i <= sz(vec); i |= i + 1) t[i]++;
}
int get(int i) {
int res = 0;
for (; i >= 0; i = (i & (i + 1)) - 1) res += t[i];
return res;
}
int getmx(int l, int r) {
if (l > r) return 0;
int deg = lg[r - l + 1];
return max(mx[deg][l], mx[deg][r - (1 << deg) + 1]);
}
int main() {
#ifdef krauch
freopen("input.txt", "r", stdin);
#endif
scanf("%d%d", &n, &Q);
forn(i, 1, n) {
scanf("%d%d", a + i, b + i);
if (a[i] > b[i]) {
swap(a[i], b[i]);
flip[i] = 1;
}
vec.eb(a[i], i);
vec.eb(b[i], n + i);
}
forn(i, 1, Q) {
scanf("%d", c + i);
vec.eb(c[i], 2 * n + i);
}
sort(all(vec));
int cnt = 1;
forn(i, 1, sz(vec) - 1) {
if (i && vec[i - 1].F != vec[i].F) ++cnt;
if (vec[i].S <= n) vala[vec[i].S] = cnt;
else if (vec[i].S <= 2 * n) valb[vec[i].S - n] = cnt;
else c[vec[i].S - 2 * n] = cnt;
}
forn(i, 1, n) {
qr[valb[i]].eb(i);
}
forn(i, 1, Q) {
g[c[i]].eb(i);
mx[0][c[i]] = i;
}
forn(i, 1, C) {
forn(j, 1, sz(vec) - (1 << i) + 1) {
mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << (i - 1))]);
}
}
forn(i, 2, sz(vec)) lg[i] = lg[i >> 1] + 1;
for1(i, sz(vec), 1) {
for (auto it : g[i]) {
upd(sz(vec) - it);
}
for (auto it : qr[i]) {
int kek = getmx(vala[it], valb[it] - 1);
if (kek == 0) {
if ((get(sz(vec)) & 1) ^ flip[it]) ans += b[it];
else ans += a[it];
}
else {
if (get(sz(vec) - kek) & 1) ans += a[it];
else ans += b[it];
}
}
}
printf("%lld\n", ans);
return 0;
}
Compilation message
factories.cpp: In function 'int main()':
factories.cpp:50:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &Q);
^
factories.cpp:52:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", a + i, b + i);
^
factories.cpp:62:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", c + i);
^
/tmp/ccsOFKeB.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccQ6ALe2.o:factories.cpp:(.text.startup+0x0): first defined here
/tmp/ccsOFKeB.o: In function `main':
grader.cpp:(.text.startup+0x279): undefined reference to `Init(int, int*, int*, int*)'
grader.cpp:(.text.startup+0x307): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status
