#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)
using namespace std;
const int nax = 6e5 + 111;
const int pod = (1 << 20);
int n, k;
int a[nax];
int b[nax];
int q[nax];
vector <int> val;
vector <int> gao[nax];
int pos(int x) {
return (int) (lower_bound(val.begin(), val.end(), x) - val.begin());
}
struct seg {
int t[2 * pod];
void init() {
for(int i = 1; i < 2 * pod; ++i)
t[i] = 0;
}
void add(int x, int c) {
x += pod;
assert(x < 2 * pod);
t[x] = max(t[x], c);
x /= 2;
while(x) {
t[x] = max(t[2 * x], t[2 * x + 1]);
x /= 2;
}
}
int query(int l, int r) {
r++;
int res = 0;
for(l += pod, r += pod; l < r; l /= 2, r /= 2) {
if(l & 1)
res = max(res, t[l++]);
if(r & 1)
res = max(res, t[--r]);
}
return res;
}
} ja;
struct fen {
int t[nax];
void init() {
for(int i = 0; i < nax; ++i)
t[i] = 0;
}
void add(int x, int c) {
assert(x < nax);
for(; x < nax; x += x & -x)
t[x] += c;
}
int query(int x) {
assert(x < nax);
int res = 0;
for(; 0 < x; x -= x & -x)
res += t[x];
return res;
}
int sum(int l, int r) {
return query(r) - query(l - 1);
}
} on;
int main() {
assert(0);
ja.init();
on.init();
val.pb(-1);
scanf("%d %d", &n, &k);
for(int i = 1; i <= n; ++i) {
scanf("%d", a + i);
scanf("%d", b + i);
val.pb(a[i]);
val.pb(b[i]);
}
for(int i = 1; i <= k; ++i) {
scanf("%d", q + i);
val.pb(q[i]);
}
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
for(int i = 1; i <= n; ++i) {
a[i] = pos(a[i]);
b[i] = pos(b[i]);
if(i <= k)
q[i] = pos(q[i]);
}
for(int i = 1; i <= k; ++i) {
ja.add(q[i], i);
gao[q[i]].pb(i);
}
ll sum = 0;
int Last = ss(val);
vector <int> v;
for(int i = 1; i <= n; ++i)
v.pb(i);
sort(v.begin(), v.end(), [](int x, int y) {
return max(a[x], b[x]) < max(a[y], b[y]);
});
for(int i = n - 1; 0 <= i; --i) {
int ind = v[i];
for(int j = max(a[ind], b[ind]); j < Last; ++j)
for(auto it : gao[j])
on.add(it, 1);
Last = max(a[ind], b[ind]);
int wsk = ja.query(min(a[ind], b[ind]), max(a[ind], b[ind]) - 1);
int hop = on.sum(wsk + 1, k);
if(hop % 2 == 0) {
sum += val[a[ind]];
}
else {
sum += val[b[ind]];
}
}
printf("%lld", sum);
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:92: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:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", a + i);
~~~~~^~~~~~~~~~~~~
fortune_telling2.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", b + i);
~~~~~^~~~~~~~~~~~~
fortune_telling2.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", q + i);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
34 ms |
29048 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 |
34 ms |
29048 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 |
34 ms |
29048 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
