#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define finish(x) return cout << x << endl, 0;
struct wavelet {
int lo, mid, hi;
vector<int> b;
wavelet *l = 0, *r = 0;
wavelet(int x, int y) {
lo = x, hi = y, mid = x + (y - x) / 2;
}
wavelet(vector<int> &a, int x, int y) {
lo = x, hi = y, mid = x + (y - x) / 2;
for (auto &i : a) push_back(i);
}
// insert a value at the back
void push_back(int v) {
if (v < lo || v > hi || lo == hi) return;
if (!b.size()) {
b.push_back(0);
l = new wavelet(lo, mid);
r = new wavelet(mid + 1, hi);
}
if (v <= mid) {
b.push_back(b.back() + 1);
this->l->push_back(v);
}
else {
b.push_back(b.back());
this->r->push_back(v);
}
}
// erase the value at the back
// returns true if the wavelet node should be deleted
bool pop_back() {
if (lo == hi) return false;
if (b[b.size() - 2] < b[b.size() - 1]) {
if (this->l->pop_back()) delete l;
}
else if (this->r->pop_back()) delete r;
b.pop_back();
return b.size() == 1;
}
// incoming random operations?:
// counts the amount of integers (<= x) in the subarray [l, r].
int celt(int l, int r, int x) {
if (l > r || lo > x) return 0;
if (hi <= x) return r - l + 1;
return this->l->celt(b[l - 1] + 1, b[r], x) + this->r->celt(l - b[l - 1], r - b[r], x);
}
// returns the k_th minimal value in the subarray [l, r].
int kth(int l, int r, int k) {
if (lo == hi) return lo;
if (b[r] - b[l - 1] >= k)
return this->l->kth(b[l - 1] + 1, b[r], k);
return this->r->kth(l - b[l - 1], r - b[r], k - (b[r] - b[l - 1]));
}
};
int n, k, x, y;
vector <int> a, b, t;
wavelet w(0, 1e9);
int larger(int l, int r, int x){
return r - l + 1 - w.celt(l, r, x - 1);
}
int smaller(int l, int r, int x){
return w.celt(l, r, x);
}
int solve(int a, int b){
if(larger(0, k - 1, b) + smaller(0, k - 1, a) == n){
int val = larger(0, k - 1, b);
if(val % 2) return b;
return a;
}
int l = 0, r = n - 1;
while(l <= r){
int mid = (l + r) / 2;
if(larger(mid, k - 1, b) + smaller(mid, k - 1, a) == k - mid) r = mid - 1;
else l = mid + 1;
}
if(b < a) swap(a, b);
int val = larger(l - 1, k - 1, b);
if(val % 2) return b;
return a;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> k;
for(int i = 0 ; i < n && cin >> x >> y ; i++)
a.push_back(x), b.push_back(y);
for(int i = 0 ; i < k && cin >> x ; i++)
w.push_back(x);
ll ans = 0;
for(int i = 0 ; i < n ; i++)
ans += solve(a[i], b[i]);
cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
3576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
3576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
3576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
