#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);
return;
}
else{
int mid = (tl+tr)/2;
if(tl == tr) return;
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;
}
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(max(a[0], a[1]) < max(b[0], b[1])) return true;
return false;
}
int32_t main(){
ios::sync_with_stdio(false); cin.tie(0);
int n, k;
cin >> n >> k;
vector <array <long long, 3>> vvv;
vector <int> valores;
for(long long i = 1;i <= n;i++){
long long a, b;
cin >> a >> b;
vvv.push_back({a, b, i});
valores.push_back(a);
valores.push_back(b);
}
map <long long, int> compressao;
vector <int> qr;
for(int i = 0;i < k;i++){
int q;
cin >> q;
qr.push_back(q);
valores.push_back(q);
}
sort(valores.begin(), valores.end());
for(int i = 0;i < valores.size();i++){
compressao[valores[i]] = i+1;
}
vector <array <int, 3>> vv;
for(auto &x : vvv){
x[0] = compressao[x[0]];
x[1] = compressao[x[1]];
array <int, 3> aux;
aux[0] = x[0];
aux[1] = x[1];
aux[2] = x[2];
vv.push_back(aux);
}
for(auto &x : qr){
x = compressao[x];
}
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];
//cout << v[i+1][0] << ' ' << v[i+1][1] << '\n';
}
seg.build(1,1, n);
for(int i = 0;i < k;i++){
int q = qr[i];
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 << res << '\n';
}
Compilation message
fortune_telling2.cpp: In function 'int32_t main()':
fortune_telling2.cpp:104:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int i = 0;i < valores.size();i++){
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
