| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 169252 | wolfris | 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.
#include <iostream>
#include <algorithm>
using namespace std;
long long n, k, a[200015], b[200015], g[200015], c[200015], x[200015], cnt[200015], BIT[200015], IT[1000015];
int getnum(int x) {
int res = 0;
for (x = upper_bound(c + 1, c + k + 1, x) - c; x <= k; x += x & -x)
res += BIT[x];
return res;
}
void addup(int x) {
for (x = lower_bound(c + 1, c + k + 1, x) - c; x >= 1; x -= x & -x)
++BIT[x];
}
void update(int x, int p, int k, int l, int r) {
if (x < c[l] || c[r] < x) return;
IT[k] = max(IT[k], p);
if (l < r)
update(x, p, 2 * k, l, (l + r) / 2),
update(x, p, 2 * k + 1, (l + r) / 2 + 1, r);
}
int getpos(int a, int b, int k, int l, int r) {
if (b < c[l] || c[r] < a) return 0;
if (a <= c[l] && c[r] <= b) return IT[k];
return max(getpos(a, b, 2 * k, l, (l + r) / 2), getpos(a, b, 2 * k + 1, (l + r) / 2 + 1, r));
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i] >> b[i];
if (a[i] > b[i])
swap(a[i], b[i]),
g[i] = 1;
}
for (int i = 1; i <= k; ++i)
cin >> x[i], c[i] = x[i];
sort(c + 1, c + k + 1);
for (int i = k; i >= 1; --i)
cnt[i] = getnum(x[i]), addup(x[i]),
update(x[i], i, 1, 1, k);
long long res = 0;
for (int i = 1; i <= n; ++i) {
int p = getpos(a[i], b[i] - 1, 1, 1, k);
if (p) {
if (cnt[p] & 1) res += a[i];
else res += b[i];
}
else {
if (getnum(b[i]) & 1) {
if (g[i]) res += a[i];
else res += b[i];
}
else {
if (g[i]) res += b[i];
else res += a[i];
}
}
}
cout << res;
}