#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
int readint(){
char a = 255;
int x = 0;
while(!(a >= '0' && a <= '9'))a = getchar();
while(a >= '0' && a <= '9') x = 10*x + (a - '0') , a = getchar();
return x;
}
struct card{
int a , b;
bool flip = false;
int ppos;
} v[200005];
int n , k ;
class BIT{
/*
MAGIA DO GATINHO .
∧＿∧
（｡･ω･｡)つ━☆・*。
⊂ ノ ・゜+.
しーＪ °。+ *´¨)
.• ´¸.•*´¨) ¸.•*¨)
(¸.•´ (¸.•'* ☆
*/
public:
void set_size(int n){
binary_index_tree.resize(n);
}
int get(int x){
if(x == 0) return 0;
int s = 0;
for(int i = x ; i > 0 ; i-=(i&-i)) s+= binary_index_tree[i];
return s;
}
void add(int x , int vl){
for(int i = x ; i < binary_index_tree.size() ; i+= (i&-i)) binary_index_tree[i] += vl;
}
private :
vector<int> binary_index_tree;
};
struct node{
node *left = nullptr , *right = nullptr;
int rmqid = - 1;
};
node *treex;
int rmq(node *& tree , int x , int y ,int l = 0 , int r = 1000000009){
int mid = (l+r)/2;
if(l == x && r == y){
return tree->rmqid;
}
if(y <= mid){
if(tree->left == nullptr) return -1;
return rmq(tree->left, x , y , l, mid);
}
else if(x > mid){
if(tree->right == nullptr) return -1;
return rmq(tree->right , x , y , mid + 1, r);
}
else{
int a = - 1 , b = - 1;
if(tree->left != nullptr) a = rmq(tree->left , x , mid , l ,mid);
if(tree->right != nullptr) b = rmq(tree->right , mid + 1 , y , mid + 1 , r);
return max(a,b);
}
}
void update(node *& tree , int x , int vl ,int l = 0 , int r = 1000000009){
int mid = (l+r)/2;
if(l ==r && l ==x){
tree->rmqid = max(tree->rmqid , vl);
return ;
}
if(x <=mid){
if(tree->left == nullptr) tree->left = new node();
update(tree->left , x , vl , l , mid);
}
else{
if(tree->right == nullptr) tree->right = new node();
update(tree->right , x, vl , mid + 1 , r);
}
int a = -1 , b = -1;
if(tree->left != nullptr) a = tree->left->rmqid;
if(tree->right != nullptr) b = tree->right->rmqid;
tree->rmqid = max(a,b);
}
vector<pair<int,int> > sweep[200005];
long long ans = 0;
int main(){
n = readint() , k = readint();
for(int i = 0 ; i < n ; i ++){
v[i].a = readint() , v[i].b = readint();
if(v[i].a > v[i].b) swap(v[i].a , v[i].b) , v[i].flip = 1;
}
treex = new node();
vector<pii> rw(k);
for(int i = 0 ; i < k ; i ++){
rw[i].first = readint();
rw[i].second = i;
update(treex , rw[i].first, rw[i].second);
}
BIT bitx;
bitx.set_size(250000);
sort(rw.begin() , rw.end());
for(int i = 0 ; i < n ; i++){
int pos = -1;
if(v[i].a < v[i].b) pos = rmq(treex , v[i].a, v[i].b - 1);
int l = 0 , r = k - 1;
int a = -1;
while(l<=r){
int mid = (l+r)/2;
if(rw[mid].first >= v[i].b){
r = mid - 1;
a = mid;
}
else l = mid + 1;
}
if(a != -1) sweep[a].pb(pair<int,int>(i , pos + 1));
else ans += (v[i].flip ? v[i].b : v[i].a);
}
for(int i = k - 1 ; i >= 0 ; i--){
bitx.add(rw[i].second + 1 , +1);
for(int j = 0 ; j < sweep[i].size() ; j++){
pii u = sweep[i][j];
int L = bitx.get(200005) - bitx.get(u.second);
if(u.second == 0){
L += v[u.first].flip;
if(L%2){
ans += v[u.first].b;
}
else ans += v[u.first].a;
}
else{
if(L%2){
ans += v[u.first].a;
}
else ans += v[u.first].b;
}
}
}
printf("%lld\n" , ans);
}
Compilation message
fortune_telling2.cpp: In member function 'void BIT::add(int, int)':
fortune_telling2.cpp:42:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = x ; i < binary_index_tree.size() ; i+= (i&-i)) binary_index_tree[i] += vl;
~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:132:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0 ; j < sweep[i].size() ; j++){
~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
9848 KB |
Output is correct |
| 2 |
Correct |
12 ms |
9960 KB |
Output is correct |
| 3 |
Incorrect |
12 ms |
10016 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
15060 KB |
Output is correct |
| 2 |
Incorrect |
72 ms |
20252 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
429 ms |
95352 KB |
Output is correct |
| 2 |
Correct |
597 ms |
96396 KB |
Output is correct |
| 3 |
Incorrect |
797 ms |
97140 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
