#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
using ll = long long;
typedef pair<int, int> ii;
const int N = 200100;
int n, k, a[N], b[N];
int Log[N], rmq[N][20];
int bit[N], ans[N];
vector <ii> vec, g[N];
void upd(int idx, int val) {
for (; idx; idx -= idx & -idx) {
bit[idx] += val;
}
}
int get(int idx) {
int re = 0;
for (; idx <= k; idx += idx & -idx) {
re += bit[idx];
}
return re;
}
int get(int l, int r) {
int lg = Log[r - l + 1];
return max(rmq[l][lg], rmq[r - (1 << lg) + 1][lg]);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i] >> b[i];
}
for (int x, i = 1; i <= k; ++i) {
cin >> x;
vec.push_back(ii(x, i));
}
Log[0] = Log[1] = 0;
for (int i = 2; i <= n; ++i) Log[i] = Log[i / 2] + 1;
sort(vec.begin(), vec.end());
for (int i = 0; i < vec.size(); ++i) rmq[i][0] = vec[i].y;
for (int j = 1; j < 20; ++j) {
for (int i = 1; i + (1 << j) <= n + 1; ++i) {
rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << j - 1)][j - 1]);
}
}
for (int i = 1; i <= n; ++i) {
int lb = min(a[i], b[i]), rb = max(a[i], b[i]);
int l = lower_bound(vec.begin(), vec.end(), ii(lb, -1)) - vec.begin();
int r = lower_bound(vec.begin(), vec.end(), ii(rb, -1)) - vec.begin() - 1;
int pos = 0;
if (l <= r) {
pos = get(l, r);
if (a[i] < b[i]) swap(a[i], b[i]);
}
g[r + 1].push_back(ii(i, pos + 1));
}
for (int i = k - 1; i >= 0; --i) {
upd(vec[i].y, 1);
for (ii e : g[i]) ans[e.x] = get(e.y) & 1;
}
ll sum = 0;
for (int i = 1; i <= n; ++i) {
sum += ans[i] ? b[i] : a[i];
//cerr << i << ' ' << ans[i] << '\n';
}
cout << sum << '\n';
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:53:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (int i = 0; i < vec.size(); ++i) rmq[i][0] = vec[i].y;
| ~~^~~~~~~~~~~~
fortune_telling2.cpp:56:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
56 | rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << j - 1)][j - 1]);
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
