//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define ll long long
const int nmax = 2e5 + 5, N = 1e6;
const ll oo = 1e9 + 5, base = 311;
const int lg = 17, tx = 26;
const ll mod = 998244353;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;
int n, k;
pii c[nmax];
struct node{
int first, second, id;
}a[nmax];
int L[nmax];
struct SEG{
int tree[nmax << 2];
void update(int id, int l, int r, int u, int val){
if(l > u|| r < u)return;
if(l >= u && r <= u){
tree[id] = val;
return;
}
int mid = r + l >> 1;
update(id << 1, l, mid, u, val);
update(id << 1 | 1, mid + 1, r, u, val);
tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
}
int get(int val){
if(tree[1] < val) return 0;
int id = 1, l = 1, r = k;
while(l != r){
int mid = r + l >> 1;
if(tree[id << 1 | 1] >= val){
id = id << 1 | 1;
l = mid + 1;
}
else{
id = id << 1;
r = mid;
}
}
return l;
}
}tree;
struct BIT{
int f[nmax];
void update(int u, int val){
for(; u; u -= u&-u) f[u] += val;
}
int get(int u){
int res = 0;
for(; u <= k; u += u&-u) res += f[u];
return res;
}
}F;
int d[nmax];
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> n >> k;
for(int i = 1; i <= n; ++i) cin >> a[i].fi >> a[i].se, a[i].id = i;
for(int i = 1; i <= k; ++i) cin >> c[i].fi, c[i].se = i, d[i] = c[i].fi;
sort(a + 1, a + 1 + n, [](node a, node b){
return max(a.fi, a.se) < max(b.fi, b.se);
});
sort(c + 1, c + 1 + k);
int pos = 1;
for(int i = 1; i <= n; ++i){
while(pos <= n && c[pos].fi < max(a[i].fi, a[i].se)){
tree.update(1, 1, k, c[pos].se, c[pos].fi);
++pos;
}
L[i] = tree.get(min(a[i].fi, a[i].se));
}
pos = n;
ll ans = 0;
for(int i = n; i >= 1; --i){
while(pos >= 1 && c[pos].fi >= max(a[i].fi, a[i].se)){
F.update(c[pos].se, 1);
--pos;
}
int x = L[i];
bool idx = 0;
if(L[i] > 0){
if(d[L[i]] >= a[i].fi) idx = 0;
else idx = 1;
}
int val = F.get(L[i] + 1);
if(val & 1) idx ^= 1;
if(!idx) ans += a[i].fi;
else ans += a[i].se;
// cout << a[i].id << ' ' << L[i] << endl;
}
cout << ans;
}
/*
5 3
4 6
9 1
8 8
4 2
3 7
8 2 9
*/
Compilation message
fortune_telling2.cpp: In member function 'void SEG::update(int, int, int, int, int)':
fortune_telling2.cpp:33:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
33 | int mid = r + l >> 1;
| ~~^~~
fortune_telling2.cpp: In member function 'int SEG::get(int)':
fortune_telling2.cpp:42:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | int mid = r + l >> 1;
| ~~^~~
fortune_telling2.cpp: At global scope:
fortune_telling2.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
68 | main(){
| ^~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:95:13: warning: unused variable 'x' [-Wunused-variable]
95 | int x = L[i];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
