//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'
int n , q;
vector<arr(2)> a;
vector<int> ops;
vector<int> seg[400001];
int seginf[400001][2];
void buildSeg(int l = 0 , int r = q - 1 , int i = 1){
seginf[i][0] = l , seginf[i][1] = r;
if(l == r) seg[i].pb(ops[l]);
else{
int c = (r + l - 1) >> 1;
buildSeg(l , c , i << 1) , buildSeg(c + 1 , r , (i << 1) | 1);
seg[i].resize(r - l + 1);
merge(seg[i << 1].bg() , seg[i << 1].end() , seg[(i << 1) | 1].bg() , seg[(i << 1) | 1].end() , seg[i].bg());
}
}
int bsSeg(int i , int l , int r){
if(i == 1){
auto itr = lb(seg[i].bg() , seg[i].end() , l);
if(itr == seg[i].end() or *itr > r) return seginf[i][0];
}
if(seginf[i][0] == seginf[i][1]) return seginf[i][1] + 1;
auto itr = lb(seg[(i << 1) | 1].bg() , seg[(i << 1) | 1].end() , l);
if(itr != seg[i].end() and *itr <= r) return bsSeg((i << 1) | 1 , l , r);
return bsSeg(i << 1 , l , r);
}
int cntSeg(int l , int r , int i , int val){
if(seginf[i][0] >= l and seginf[i][1] <= r) return (r - l + 1 - int(lb(seg[i].bg() , seg[i].end() , val) - seg[i].bg()));
if(seginf[i][1] >= l and seginf[i][0] <= r) return (cntSeg(l , r , i << 1 , val) + cntSeg(l , r , (i << 1) | 1 , val));
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for(int i = 0 ; i < n ; i++){
int d1 , d2;
cin >> d1 >> d2;
a.pb({d1 , d2});
}
for(int i = 0 ; i < q ; i++){
int d;
cin >> d;
ops.pb(d);
}
ll o = 0;
buildSeg();
for(auto el : a){
ll lsto = o;
if(el[0] == el[1]) o += (1ll * el[0]);
else if(el[0] < el[1]){
int inx = bsSeg(1 , el[0] , el[1] - 1);
int d = 0;
if(inx < q) d = cntSeg(inx , q - 1 , 1 , el[1]);
if(inx == 0){
if((d & 1)) o += (1ll * el[1]);
else o += (1ll * el[0]);
}else{
if((d & 1)) o += (1ll * el[0]);
else o += (1ll * el[1]);
}
}else if(el[1] < el[0]){
int inx = bsSeg(1 , el[1] , el[0] - 1);
int d = 0;
if(inx < q) d = cntSeg(inx , q - 1 , 1 , el[1]);
if((d & 1)) o += (1ll * el[1]);
else o += (1ll * el[0]);
}
}
cout << o;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:67:12: warning: unused variable 'lsto' [-Wunused-variable]
67 | ll lsto = o;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
10840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
10840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
10840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
