#include <bits/stdc++.h>
using namespace std;
struct card{
int a , b;
bool flip = false;
bool newvl = true;
} v[200005];
int n , k ;
struct node{
node *left = NULL, *right = NULL;
int rmqidx = -1;
} ;
node * treex ;
void update(node *&tree , int x , int vl , int l = 0 , int r = 1000000007){
int mid = (l+r)/2;
if(l == r){
tree->rmqidx = max(tree->rmqidx , vl);
return ;
}
if(x <= mid){
if(tree->left == NULL) tree->left = new node();
update(tree->left , x , vl , l , mid);
}
else{
if(tree->right == NULL) tree->right = new node();
update(tree->right, x , vl , mid + 1, r);
}
int xl = -1 , xr = -1;
if(tree->left != NULL) xl = tree->left->rmqidx;
if(tree->right != NULL) xr = tree->right->rmqidx;
tree->rmqidx = max(xl, xr);
return ;
}
int query(node *&tree , int x , int y , int l = 0 , int r = 1000000007 ){
int mid = (l+r)/2;
if(x == l && y == r){
return tree->rmqidx;
}
if(y <= mid){
if(tree->left == NULL) return -1;
return query(tree->left, x , y , l, mid);
}
else if(x > mid){
if(tree->right == NULL) return -1;
return query(tree->right , x , y, mid + 1 , r);
}
else{
int xl = -1 , xr = -1;
if(tree->left != NULL) xl = query(tree->left, x , mid , l ,mid);
if(tree->right != NULL) xr = query(tree->right , mid + 1 , y , mid + 1 , r);
return max(xl, xr);
}
}
struct nd{
nd *left = NULL, * right = NULL;
int sj = 0 ;
};
nd *treey;
void updatevl(nd *& tree , int x , int vl, int l = 0 , int r = 1000000007){
int mid = (l+r)/2;
if( l== r){
tree->sj += vl;
return ;
}
if(x <= mid){
if(tree->left == NULL) tree->left = new nd();
updatevl(tree->left, x , vl , l , mid);
}
else{
if(tree->right == NULL) tree->right = new nd();
updatevl(tree->right , x , vl , mid + 1 , r);
}
int a = 0 , b = 0;
if(tree->left != NULL){
a += tree->left->sj;
}
if(tree->right != NULL){
b += tree->right->sj;
}
tree->sj = a + b;
}
int queryvl(nd *& tree , int x , int y , int l = 0 , int r = 1000000007){
int mid = (l+r)/2;
if(l == x && r == y){
return tree->sj;
}
if(y <= mid){
if(tree->left == NULL) return 0;
return queryvl(tree->left , x , y ,l , mid);
}
else if(x > mid){
if(tree->right == NULL) return 0;
return queryvl(tree->right , x , y , mid + 1 , r);
}
else{
int a = 0 , b = 0;
if(tree->left != NULL) a = queryvl(tree->left, x , mid , l , mid);
if(tree->right != NULL) b = queryvl(tree->right , mid + 1 , y , mid + 1 , r);
return (a + b);
}
}
bool cmp(card x , card y){
if(x.b == y.b){
return x.a > y.a;
}
return x.b < y.b;
}
int main(){
scanf("%d%d" , &n , &k);
for(int i = 0 ;i < n ; i ++){
scanf("%d%d" , &v[i].a , &v[i].b);
if(v[i].a > v[i].b){
swap(v[i].a , v[i].b);
v[i].flip = 1;
}
}
treex = new node();
treey = new nd();
multiset< pair<int,int> > taro;
vector<int> aa;
for(int i = 0 ; i < k ; i++){
int x;
scanf("%d" , &x);
aa.push_back(x);
taro.insert(pair<int,int>(x , i));
update(treex , x , i);
updatevl(treey , x , +1);
}
long long ans = 0LL;
int j =0;
sort(v , v + n , cmp);
for(int i = 0 ; i < n ; i ++){
int U = -1;
if(v[i].a < v[i].b)
U = query(treex , v[i].a , v[i].b - 1);
if(U == -1){
v[i].newvl = 0;
int Z = queryvl(treey , v[i].b , 1000000005);
if(v[i].flip) Z += 1;
if(Z%2){
ans += v[i].b;
}
else ans += v[i].a;
}
}
for(int i = 0 ; i < n; i ++){
if(v[i].newvl == 0) continue;
int U = query(treex , v[i].a , v[i].b-1);
while(j <= U){
updatevl(treey, aa[j++] , -1);
}
int R = queryvl(treey , v[i].b , 1000000005);
if(R%2){
ans += v[i].a;
}
else ans+= v[i].b;
}
cout<<ans<<endl;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:118:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d" , &n , &k);
~~~~~^~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:120:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d" , &v[i].a , &v[i].b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d" , &x);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
3988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
14712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1324 ms |
183796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
