#include <iostream>
#include <algorithm>
#include <vector>
#define endl '\n'
#define pb push_back
#define lb(vc, x) lower_bound(vc.begin(), vc.end(), x)
#define ub(vc, x) upper_bound(vc.begin(), vc.end(), x)
#define mp make_pair
#define ll long long
using namespace std;
const int MAXN = 2e5+100;
struct query{
int i, x;
};
int max(int a, int b){
return (a > b)? a : b;
}
bool operator<(const query &a, const query &b){
return mp(a.x, a.i) < mp(b.x, b.i);
}
bool operator>(const query &a, const query &b){
return mp(a.x, a.i) > mp(b.x, b.i);
}
vector<int> seg[1 << 20];
void combine(int v){
int lc = (v << 1), rc = lc|1;
int pl=0, pr=0;
while(pl < seg[lc].size() and pr < seg[rc].size()){
if(seg[lc][pl] <= seg[rc][pr]){
seg[v].pb(seg[lc][pl]);
pl++;
}
else {
seg[v].pb(seg[rc][pr]);
pr++;
}
}
while(pl < seg[lc].size()){
seg[v].pb(seg[lc][pl]);
pl++;
}
while(pr < seg[rc].size()){
seg[v].pb(seg[rc][pr]);
pr++;
}
}
int get_max(int v, int vl, int vr, int l, int r){
if(vl > r or vr < l) return 0;
if(l <= vl and vr <= r)
return seg[v].back();
int vm = (vl + vr) >> 1;
int getl = get_max((v<<1), vl, vm, l, r);
int getr = get_max((v<<1)|1, vm+1, vr, l, r);
return max(getl, getr);
}
int count_gte(int v, int vl, int vr, int l, int r, int x){
if(vl > r or vr < l) return 0;
if(l <= vl and vr <= r)
return seg[v].end() - lb(seg[v], x);
int vm = (vl + vr) >> 1;
int getl = count_gte((v<<1), vl, vm, l, r, x);
int getr = count_gte((v<<1)|1, vm+1, vr, l, r, x);
return getl + getr;
}
int n, sn, k;
int a[MAXN], b[MAXN];
vector<query> queries;
int main(){
// ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> k;
for(int i=0; i<n; i++)
cin >> a[i] >> b[i];
for(int i=0; i<k; i++){
int x;
cin >> x;
queries.pb({i, x});
}
sort(queries.begin(), queries.end());
reverse(queries.begin(), queries.end());
sn = 1;
while(sn < k) sn <<= 1;
for(int i=0; i<k; i++)
seg[i + sn].pb(queries[i].i);
for(int i=(sn - 1); i>=0; i--)
combine(i);
ll sm = 0;
for(int i=0; i<n; i++){
query qa = {0, a[i]}, qb = {0, b[i]};
if(a[i] <= b[i])
swap(qa, qb);
int l = (lower_bound(queries.begin(), queries.end(), qa, greater<query>()) - queries.begin());
int r = (upper_bound(queries.begin(), queries.end(), qb, greater<query>()) - queries.begin());
r--;
int gt = 0, mx;
// cout << l << ' ' << r << endl;
if(l <= r){
mx = get_max(1, 1, sn, l, r);
// cout << "MX: " << mx << endl;
gt = count_gte(1, 1, sn, r, k, mx);
}
// cout << gt << endl;
if(a[i] > b[i])
gt++;
if(gt&1)
// cout << b[i] << ' ';
sm += b[i];
else
// cout << a[i] << ' ';
sm += a[i];
}
// cout << endl;
cout << sm << endl;
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'void combine(int)':
fortune_telling2.cpp:39:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | while(pl < seg[lc].size() and pr < seg[rc].size()){
| ~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:39:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | while(pl < seg[lc].size() and pr < seg[rc].size()){
| ~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:50:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | while(pl < seg[lc].size()){
| ~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:55:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | while(pr < seg[rc].size()){
| ~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
26332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
26332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
26332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
