#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ii pair <int, int>
#define x first
#define y second
#define db(x) cerr << #x << " = " << x << endl;
#define _ << ", " <<
using namespace __gnu_pbds;
using namespace std;
inline void read(int &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void read(long long &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void writeln(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar('\n');}
inline void write(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar(' ');}
const int N = 2e5 + 7;
const int oo = 1e9 + 7;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int n, k, g;
ii card[N];
int t[N], rev[5 * N];
vector <int> v;
vector <ii> vt;
map <int, int> mp;
long long res;
struct segTree{
int tree[4 * N], l[4 * N], h[4 * N];
int leaf[N];
void Build(int x, int low, int high){
l[x] = low; h[x] = high;
if (low == high){
leaf[low] = x;
tree[x] = -oo;
}
else{
int mid = low + high >> 1;
Build(2 * x, low, mid);
Build(2 * x + 1, mid + 1, high);
tree[x] = max(tree[2 * x], tree[2 * x + 1]);
}
}
void Update(int x, int val){
x = leaf[x];
tree[x] = val;
while (1){
x >>= 1;
if (x == 0) break;
tree[x] = max(tree[2 * x], tree[2 * x + 1]);
}
}
int Query(int x, int i, int j){
if (l[x] > j || h[x] < i) return -oo;
if (l[x] >= i && h[x] <= j) return tree[x];
int L = Query(2 * x, i, j);
int R = Query(2 * x + 1, i, j);
return max(L, R);
}
}IT;
inline void compressData(){
sort(v.begin(), v.end());
mp[++g] = v[0];
rev[g] = v[0];
for (int i = 1; i < v.size(); i++)
if (v[i] != v[i - 1]){
mp[v[i]] = ++g;
rev[g] = v[i];
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
read(n); read(k);
for (int i = 1; i <= n; i++){
read(card[i].x); read(card[i].y);
v.push_back(card[i].x);
v.push_back(card[i].y);
}
for (int i = 1; i <= k; i++){
read(t[i]);
v.push_back(t[i]);
}
compressData();
IT.Build(1, 1, g);
for (int i = 1; i <= k; i++){
t[i] = mp[t[i]];
vt.push_back(ii(t[i], i));
IT.Update(t[i], i);
}
sort(vt.begin(), vt.end());
for (int i = 1; i <= n; i++){
card[i].x = mp[card[i].x];
card[i].y = mp[card[i].y];
}
sort(card + 1, card + n + 1, [] (ii a, ii b) {
return max(a.x, a.y) > max(b.x, b.y);
});
ordered_set certain; // ordered_set
for (int i = 1; i <= n; i++){
int mn = min(card[i].x, card[i].y);
int mx = max(card[i].x, card[i].y);
/* 3 types of flip
- T < mn: nothing done
- mn <= T <= mx: will flip the mx value to upper face
- mx <= T: will flip the card no matter what face is up
KEY OBSERVATION:
- If the latest 2nd-type operation happens, it will result in card with mx value on top
- In contrast, mx value is already on top
====> mx value is always on top if there is a 2nd-type operation.
*/
while (vt.size() && vt.back().x >= mx){
certain.insert(vt.back().y);
vt.pop_back();
}
int lastBetween = IT.Query(1, mn, mx);
int remainingFlip = (certain.size() - certain.order_of_key(lastBetween)) % 2;
int id;
if (lastBetween == -oo)
id = (remainingFlip ? card[i].y : card[i].x);
else
id = (remainingFlip ? mn : mx);
res += rev[id];
}
writeln(res);
}
Compilation message
fortune_telling2.cpp: In member function 'void segTree::Build(int, int, int)':
fortune_telling2.cpp:43:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = low + high >> 1;
~~~~^~~~~~
fortune_telling2.cpp: In function 'void compressData()':
fortune_telling2.cpp:74:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < v.size(); i++)
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
760 KB |
Output is correct |
| 2 |
Correct |
4 ms |
632 KB |
Output is correct |
| 3 |
Correct |
4 ms |
760 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
760 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
760 KB |
Output is correct |
| 2 |
Correct |
4 ms |
632 KB |
Output is correct |
| 3 |
Correct |
4 ms |
760 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
760 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
760 KB |
Output is correct |
| 2 |
Correct |
4 ms |
632 KB |
Output is correct |
| 3 |
Correct |
4 ms |
760 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
760 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
