#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define left defined_left
#define right defined_right
const int N = 2e5 + 5, Q = N;
int n, q, a[N], b[N], t[Q], sp[__lg(N) + 3][N], m;
vector<int> arr = {0};
int get(int x) {
return lower_bound(arr.begin(), arr.end(), x) - arr.begin();
}
int get_max(int l, int r) {
int k = __lg(r - l + 1);
return max(sp[k][l], sp[k][r - (1 << k) + 1]);
}
struct Node {
int sum;
Node *left, *right;
Node(int sum = 0, Node *left = nullptr, Node *right = nullptr):
sum(sum), left(left), right(right) {}
Node *go_left() {
if (left == nullptr)
left = new Node();
return left;
}
Node *go_right() {
if (right == nullptr)
right = new Node();
return right;
}
};
Node *v[N];
Node* update(int x, Node *cur, int l, int r) {
if (l == r) return new Node(cur->sum + 1);
int mid = (l + r) / 2;
Node *res = new Node();
if (x <= mid) {
res->left = update(x, cur->go_left(), l, mid);
res->right = cur->right;
} else {
res->left = cur->left;
res->right = update(x, cur->go_right(), mid + 1, r);
}
res->sum = res->go_left()->sum + res->go_right()->sum;
return res;
}
int get_sum(int x, int y, Node *cur, int l, int r) {
if (l > y || r < x) return 0;
if (x <= l && r <= y) return cur->sum;
int mid = (l + r) / 2;
return get_sum(x, y, cur->go_left(), l, mid) + get_sum(x, y, cur->go_right(), mid + 1, r);
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
if (fopen("SwapCard.inp", "r"))
freopen("SwapCard.inp", "r", stdin),
freopen("SwapCard.out", "w", stdout);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
arr.emplace_back(a[i]);
arr.emplace_back(b[i]);
}
for (int i = 1; i <= q; i++) {
cin >> t[i];
arr.emplace_back(t[i]);
}
sort(arr.begin(), arr.end());
arr.resize(unique(arr.begin(), arr.end()) - arr.begin());
m = arr.size() - 1;
for (int i = 1; i <= n; i++)
a[i] = get(a[i]), b[i] = get(b[i]);
for (int i = 1; i <= q; i++) {
t[i] = get(t[i]);
sp[0][t[i]] = i;
}
v[q + 1] = new Node();
for (int i = q; i > 0; i--)
v[i] = update(t[i], v[i + 1], 1, m);
for (int k = 1; (1 << k) <= q; k++)
for (int i = 1; i + (1 << k) - 1 <= q; i++)
sp[k][i] = max(sp[k - 1][i], sp[k - 1][i + (1 << (k - 1))]);
ll ans = 0;
for (int i = 1; i <= n; i++) {
if (a[i] == b[i]) {
ans += arr[a[i]];
continue;
}
bool dummy = false;
if (a[i] < b[i]) {
dummy = true;
swap(a[i], b[i]);
}
int pos = get_max(b[i], a[i] - 1);
bool greater_ = 1 ^ (get_sum(a[i], m, v[pos + 1], 1, m) & 1);
if (pos == 0) greater_ ^= dummy;
int cur;
if (greater_) cur = arr[a[i]];
else cur = arr[b[i]];
// cerr << "At i = " << i << ", cur = " << cur << '\n';
ans += cur;
}
cout << ans;
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'int32_t main()':
fortune_telling2.cpp:70:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | freopen("SwapCard.inp", "r", stdin),
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:71:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | freopen("SwapCard.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
13148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
13148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
13148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
