# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
119430 | IOrtroiii | Fortune Telling 2 (JOI14_fortune_telling2) | C++14 | 92 ms | 22940 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 <bits/stdc++.h>
using namespace std;
const int N = 200200;
int n, q;
int x[N], y[N], z[N];
bool sw[N];
bool ft[N];
vector<pair<int, int>> vals;
int rmq[18][N];
vector<pair<int, int>> qs[N];
void mdf(int v) {
for (; v > 0; v -= v & -v) {
ft[v] ^= true;
}
}
bool get(int v) {
bool ans = false;
for (; v <= q; v += v & -v) {
ans ^= ft[v];
}
return ans;
}
int get(int l, int r) {
int LG = __lg(r - l + 1);
return max(rmq[LG][l], rmq[LG][r - (1 << LG) + 1]);
}
int main() {
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; ++i) {
scanf("%d %d", x + i, y + i);
}
for (int i = 1; i <= q; ++i) {
scanf("%d", z + i);
vals.emplace_back(z[i], i);
}
sort(vals.begin(), vals.end());
for (int i = 0; i < q; ++i) {
rmq[0][i + 1] = vals[i].second;
}
for (int i = 1; i < 17; ++i) {
for (int j = 1; j + (1 << i) - 1 <= q; ++j) {
rmq[i][j] = max(rmq[i - 1][j], rmq[i - 1][j + (1 << i - 1)]);
}
}
for (int i = 1; i <= n; ++i) {
int l = min(x[i], y[i]), r = max(x[i], y[i]);
l = lower_bound(vals.begin(), vals.end(), make_pair(l, 0)) - vals.begin() + 1;
r = lower_bound(vals.begin(), vals.end(), make_pair(r, 0)) - vals.begin();
int last = 0;
if (l <= r) {
last = get(l, r);
if (x[i] < y[i]) {
swap(x[i], y[i]);
}
}
qs[r].emplace_back(i, last + 1);
}
for (int i = q - 1; i >= 0; --i) {
mdf(vals[i].second);
for (auto v : qs[i]) {
sw[v.first] = get(v.second);
}
}
long long ans = 0;
for (int i = 1; i <= n; ++i) {
if (sw[i]) {
ans += y[i];
} else {
ans += x[i];
}
}
printf("%lld\n", ans);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |