#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
int N, K;
pair<int,int> A[MAXN + 10];
int bit[MAXN + 10];
int X[MAXN + 10];
set<int> spos;
void inc(int i) {
for(i++; i <= K; i += i & (-i)) {
bit[i] ^= 1;
}
}
int sum(int r) {
int res = 0;
for(r++; r > 0; r -= r & (-r)) {
res ^= bit[r];
}
return res;
}
int sum(int l, int r) {
return sum(r) ^ sum(l);
}
int mx[4 * MAXN + 10];
void mx_upd(int cn, int b, int e, int i, int x) {
if(i < b || i > e) return;
if(b == e) {
mx[cn] = x;
return;
}
int m = (b + e) / 2;
mx_upd(cn << 1, b, m, i, x);
mx_upd(cn << 1 | 1, m+1, e, i, x);
mx[cn] = max(mx[cn << 1], mx[cn << 1 | 1]);
}
int nxt(int cn, int b, int e, int x) {
if(mx[cn] < x) return -1;
if(b == e) return b;
int m = (b + e) / 2;
if(mx[cn<<1|1] < x) return nxt(cn << 1, b, m, x);
return nxt(cn << 1 | 1, m+1, e, x);
}
int solve(int i) {
int l = nxt(1, 0, K-1, min(A[i].first, A[i].second));
int p = sum(l, K-1);
if(l != -1) {
if(A[i].first < A[i].second) swap(A[i].first, A[i].second);
}
if(p) return A[i].second;
else return A[i].first;
}
int main() {
scanf("%d%d", &N, &K);
for(int i = 0; i < N; i++) {
scanf("%d%d", &A[i].first, &A[i].second);
}
for(int i = 0; i < K; i++) {
scanf("%d", &X[i]);
}
sort(A, A + N,
[](pair<int,int> a, pair<int,int> b) {
int ma = max(a.first, a.second);
int mb = max(b.first, b.second);
if(ma != mb) return ma < mb;
return a < b;
});
reverse(A, A + N);
for(int i = 0; i < K; i++) {
if(X[i] < min(A[0].first, A[0].second)) continue;
if(X[i] < max(A[0].first, A[0].second)) { // S
mx_upd(1, 0, K-1, i, X[i]);
}
}
set<pair<long long,int>> st;
for(int i = 0; i < K; i++) {
st.emplace(X[i], i);
}
while(st.size() && st.rbegin()->first >= max(A[0].first, A[0].second)) {
inc(st.rbegin()->second);
st.erase(*st.rbegin());
}
long long res = solve(0);
for(int i = 1; i < N; i++) {
while(st.size() && st.rbegin()->first >= max(A[i].first, A[i].second)) {
int j = st.rbegin()->second;
mx_upd(1, 0, K-1, j, -1);
inc(j);
st.erase(*st.rbegin());
}
res += solve(i);
}
printf("%lld\n", res);
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:65:9: 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:67:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &A[i].first, &A[i].second);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:70:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &X[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
616 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
616 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
616 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
