#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 = 6e6 + 6, C = 20, 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 > vec, g[N], qr[N];
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]);
vec.eb(b[i]);
}
forn(i, 1, Q) {
scanf("%d", c + i);
vec.eb(c[i]);
}
sort(all(vec));
vec.erase(unique(all(vec)), vec.end());
forn(i, 1, n) {
vala[i] = upper_bound(all(vec), a[i]) - vec.begin();
valb[i] = upper_bound(all(vec), b[i]) - vec.begin();
qr[valb[i]].eb(i);
}
forn(i, 1, Q) {
c[i] = upper_bound(all(vec), c[i]) - vec.begin();
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
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:49:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &Q);
^
fortune_telling2.cpp:51: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);
^
fortune_telling2.cpp:61:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", c + i);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
