#include<bits/stdc++.h>
#define int long long
#define fr first
#define sc second
using namespace std;
const int N = 200010;
const int B = 200;
int v[N][2];
int blocks[N];
struct Segtree{
pair <int, int> tree[4*N]; int lazy[4*N];
pair <int, int> join(pair <int, int> a, pair <int, int> b){
return {max(a.fr, b.fr), max(a.sc, b.sc)};
}
void unlazy(int node, int l, int r){
if(lazy[node]%2) swap(tree[node].fr, tree[node].sc);
if(l != r){
lazy[2*node] += lazy[node];
lazy[2*node+1] += lazy[node];
}
lazy[node] = 0;
}
void build(int node, int l, int r){
lazy[node] = 0;
if(l == r){
tree[node] = {v[l][0], v[l][1]};
return;
}
int mid = (l+r)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
tree[node] = join(tree[2*node], tree[2*node+1]);
}
void update(int node, int l, int r, int tl, int tr, int val){
unlazy(node, tl, tr);
if(l > tr or tl > r) return;
if(l <= tl and tr <= r){
if(tree[node].first <= val) {
lazy[node]++;
unlazy(node, tl, tr);
}
else{
int mid = (tl+tr)/2;
update(2*node, l, r, tl, mid, val);
update(2*node+1, l, r, mid+1, tr, val);
}
return;
}
if(tree[node].first > val) return;
int mid = (tl+tr)/2;
update(2*node, l, r, tl, mid, val);
update(2*node+1, l, r, mid+1, tr, val);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
pair <int, int> query(int node, int l, int r, int tl, int tr){
unlazy(node, tl, tr);
if(l > tr or tl > r) return {0, 0};
if(l <= tl and tr <= r) return tree[node];
int mid = (tl+tr)/2;
return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
}
} seg;
bool comp2(array <int, 3> a, array <int, 3> b){
if(blocks[a[2]] > blocks[b[2]]) return false;
if(blocks[a[2]] < blocks[b[2]]) return true;
if(max(a[0], a[1]) < max(b[0], b[1])) return true;
return false;
}
bool comp(array <int, 3> a, array <int, 3> b){
if(min(a[0], a[1]) < min(b[0], b[1])) return true;
return false;
}
int32_t main(){
int n, k;
cin >> n >> k;
vector <array <int, 3>> vv;
for(int i = 1;i <= n;i++){
int a, b;
cin >> a >> b;
vv.push_back({a, b, i});
}
sort(vv.begin(), vv.end(), comp);
for(int i = 1;i <= n;i++){
blocks[vv[i-1][2]] = i/B;
}
sort(vv.begin(), vv.end(), comp2);
for(int i = 0;i < n;i++){
v[i+1][0] = vv[i][0];
v[i+1][1] = vv[i][1];
}
seg.build(1,1, n);
int q;
for(int i = 0;i < k;i++){
int q;
cin >> q;
seg.update(1, 1, n, 1, n, q);
}
int res = 0;
for(int i = 1;i <= n;i++){
res += seg.query(1, i, i, 1, n).first;
//cout << seg.query(1, i, i,1, n).first << ' ';
}
cout << res << '\n';
}
Compilation message
fortune_telling2.cpp: In function 'int32_t main()':
fortune_telling2.cpp:99:9: warning: unused variable 'q' [-Wunused-variable]
99 | int q;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
16976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
16976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
16976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
