#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 * trees[200005];
void persistent(nd *& old_version , nd *& nw , int x , int vl , int l = 0 , int r = 1000000007){
int mid = (l+r)/2;
if(l == r){
nw->sj = old_version->sj;
nw->sj += vl;
return ;
}
if(x <= mid){
nw->right = old_version->right;
if(nw->left == NULL) nw->left = new nd();
if(old_version->left == NULL) persistent(trees[0] , nw->left , x , vl , l, mid);
else persistent(old_version->left , nw->left, x , vl ,l ,mid);
}
else{
nw->left = old_version->left;
if(nw->right == NULL) nw->right = new nd();
if(old_version->right == NULL) persistent(trees[0] , nw->right , x , vl , mid + 1 , r);
else persistent(old_version->right , nw->right , x , vl , mid + 1 , r);
}
int a= 0 , b = 0;
if(nw->left != NULL) a = nw->left->sj;
if(nw->right != NULL) b = nw->right->sj;
nw->sj = a + b;
}
int queryvl(nd *& treel , nd *& treer , int x , int y , int l = 0 , int r = 1000000007){
int mid = (l+r)/2;
if(l == x && r == y){
return (treer->sj - treel->sj);
}
if(y <= mid){
if(treer->left == NULL) return 0;
else{
if(treel->left == NULL) return queryvl(trees[0] , treer->left , x , y , l ,mid);
else return queryvl(treel->left , treer->left , x , y , l ,mid);
}
}
else if(x > mid){
if(treer->right == NULL) return 0;
else{
if(treel->right == NULL) return queryvl(trees[0] , treer->right , x , y, mid + 1 , r);
else return queryvl(treel->right , treer->right , x , y, mid+ 1 , r);
}
}
else{
int a = 0 , b = 0;
if(treer->left != NULL){
if(treel->left == NULL) a = queryvl(trees[0] , treer->left , x , mid , l , mid);
else a = queryvl(treel->left , treer->left , x , mid , l, mid);
}
if(treer->right != NULL){
if(treel->right == NULL) b = queryvl(trees[0] , treer->right , mid +1 , y, mid +1 , r);
else b = queryvl(treel->right , treer->right , mid + 1 , y , mid + 1 , r);
}
return (a+b);
}
}
int32_t 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();
trees[0] = new nd();
vector<int> aa;
for(int i = 0 ; i < k ; i++){
int x;
scanf("%d" , &x);
aa.push_back(x);
update(treex , x , i);
trees[i+1] = new nd();
persistent(trees[i] , trees[i+1] , x , +1);
}
long long ans = 0LL;
int j =0;
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(trees[0] , trees[k] , 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);
int R = queryvl(trees[U] , trees[k] , v[i].b , 1000000005);
if(R%2){
ans += v[i].a;
}
else ans += v[i].b;
}
printf("%lld\n" , ans);
}
Compilation message
fortune_telling2.cpp: In function 'int32_t main()':
fortune_telling2.cpp:144:6: warning: unused variable 'j' [-Wunused-variable]
int j =0;
^
fortune_telling2.cpp:124: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:126: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:137: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 |
Correct |
8 ms |
4344 KB |
Output is correct |
| 2 |
Correct |
8 ms |
4428 KB |
Output is correct |
| 3 |
Correct |
9 ms |
4428 KB |
Output is correct |
| 4 |
Correct |
9 ms |
4496 KB |
Output is correct |
| 5 |
Correct |
9 ms |
4584 KB |
Output is correct |
| 6 |
Correct |
9 ms |
4688 KB |
Output is correct |
| 7 |
Correct |
8 ms |
4716 KB |
Output is correct |
| 8 |
Correct |
9 ms |
4764 KB |
Output is correct |
| 9 |
Correct |
8 ms |
4836 KB |
Output is correct |
| 10 |
Correct |
8 ms |
4836 KB |
Output is correct |
| 11 |
Correct |
9 ms |
4952 KB |
Output is correct |
| 12 |
Correct |
9 ms |
4988 KB |
Output is correct |
| 13 |
Correct |
9 ms |
5020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
18748 KB |
Output is correct |
| 2 |
Correct |
135 ms |
34100 KB |
Output is correct |
| 3 |
Correct |
207 ms |
49408 KB |
Output is correct |
| 4 |
Correct |
310 ms |
65036 KB |
Output is correct |
| 5 |
Correct |
364 ms |
66192 KB |
Output is correct |
| 6 |
Correct |
321 ms |
67352 KB |
Output is correct |
| 7 |
Correct |
268 ms |
68460 KB |
Output is correct |
| 8 |
Correct |
262 ms |
69828 KB |
Output is correct |
| 9 |
Correct |
195 ms |
69828 KB |
Output is correct |
| 10 |
Correct |
201 ms |
69828 KB |
Output is correct |
| 11 |
Correct |
188 ms |
69828 KB |
Output is correct |
| 12 |
Correct |
198 ms |
69828 KB |
Output is correct |
| 13 |
Correct |
217 ms |
73224 KB |
Output is correct |
| 14 |
Correct |
253 ms |
74688 KB |
Output is correct |
| 15 |
Correct |
257 ms |
75328 KB |
Output is correct |
| 16 |
Correct |
240 ms |
76960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1004 ms |
298220 KB |
Output is correct |
| 2 |
Correct |
1287 ms |
301192 KB |
Output is correct |
| 3 |
Correct |
1427 ms |
304948 KB |
Output is correct |
| 4 |
Execution timed out |
2031 ms |
310824 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
