#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, k, ans;
vector<pair<pair<int, int>, int>> crs;
vector<pair<int, int>> qs;
const int MXN = 200005;
int seg[MXN * 4];
int arr[MXN];
void build(int ind, int l, int r) {
if (l == r) {
seg[ind] = qs[l].second;
return;
}
int m = (l + r) / 2;
build(ind*2, l, m);
build(ind*2+1, m+1, r);
seg[ind] = max(seg[ind*2], seg[ind*2+1]);
}
int query(int ind, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return seg[ind];
if (ql > r || qr < l) return -1;
int m = (l + r) / 2;
return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr));
}
struct wavelet_tree{
#define vi vector<int>
#define pb push_back
int lo, hi;
wavelet_tree *l, *r;
vi b;
//nos are in range [x,y]
//array indices are [from, to)
wavelet_tree(int *from, int *to, int x, int y){
lo = x, hi = y;
if(lo == hi or from >= to) return;
int mid = (lo+hi)/2;
auto f = [mid](int x){
return x <= mid;
};
b.reserve(to-from+1);
b.pb(0);
for(auto it = from; it != to; it++)
b.pb(b.back() + f(*it));
//see how lambda function is used here
auto pivot = stable_partition(from, to, f);
l = new wavelet_tree(from, pivot, lo, mid);
r = new wavelet_tree(pivot, to, mid+1, hi);
}
//kth smallest element in [l, r]
int kth(int l, int r, int k){
if(l > r) return 0;
if(lo == hi) return lo;
int inLeft = b[r] - b[l-1];
int lb = b[l-1]; //amt of nos in first (l-1) nos that go in left
int rb = b[r]; //amt of nos in first (r) nos that go in left
if(k <= inLeft) return this->l->kth(lb+1, rb , k);
return this->r->kth(l-lb, r-rb, k-inLeft);
}
//count of nos in [l, r] Less than or equal to k
int LTE(int l, int r, int k) {
if(l > r or k < lo) return 0;
if(hi <= k) return r - l + 1;
int lb = b[l-1], rb = b[r];
return this->l->LTE(lb+1, rb, k) + this->r->LTE(l-lb, r-rb, k);
}
//count of nos in [l, r] equal to k
int count(int l, int r, int k) {
if(l > r or k < lo or k > hi) return 0;
if(lo == hi) return r - l + 1;
int lb = b[l-1], rb = b[r], mid = (lo+hi)/2;
if(k <= mid) return this->l->count(lb+1, rb, k);
return this->r->count(l-lb, r-rb, k);
}
~wavelet_tree(){
delete l;
delete r;
}
};
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> k;
for (int i=0; i<n; i++) {
int a, b;
cin >> a >> b;
if (a == b) {
ans += a;
continue;
}
int s = 0;
if (a > b) {
swap(a, b); s = 1;
}
crs.push_back({{a, b}, s});
}
n = crs.size();
for (int i=0; i<k; i++) {
int x;
cin >> x;
qs.push_back({x, i});
}
sort(qs.begin(), qs.end());
for (int x=0; x<k; x++) {
arr[x] = qs[x].second;
}
build(1, 0, k-1);
wavelet_tree tr(arr, arr+k, 0, k);
for (auto x: crs) {
int a = x.first.first, b = x.first.second;
int e = lower_bound(qs.begin(), qs.end(), make_pair(a, 0ll)) - qs.begin();
int f = upper_bound(qs.begin(), qs.end(), make_pair(b-1, k)) - qs.begin() - 1;
int ls = query(1, 0, k-1, e, f);
int up = x.second;
if (ls != -1) up = 1;
int flips = ((k-1)-(f+1)+1) - tr.LTE(f+1, k-1, ls);
for (int j=f+1; j<qs.size(); j++) {
if (qs[j].second > ls) flips++;
}
if (flips % 2 == 1) up = 1 - up;
if (up) ans += b;
else ans += a;
}
cout << ans << endl;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:145: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]
145 | for (int j=f+1; j<qs.size(); j++) {
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1004 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1004 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1004 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
