//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<ll , x>
#define endl '\n'
ll n , q;
vector<arr(2)> a;
vector<ll> ops;
vector<ll> seg[400001];
ll seginf[400001][2];
void buildSeg(ll l = 0 , ll r = q - 1 , ll i = 1){
seginf[i][0] = l , seginf[i][1] = r;
if(l == r) seg[i].pb(ops[l]);
else{
ll 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());
}
}
ll bsSeg(ll i , ll l , ll 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);
}
ll cntSeg(ll l , ll r , ll i , ll val){
if(seginf[i][0] >= l and seginf[i][1] <= r) return (seginf[i][1] - seginf[i][0] + 1 - (1ll * 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(ll i = 0 ; i < n ; i++){
ll d1 , d2;
cin >> d1 >> d2;
a.pb({d1 , d2});
}
for(ll i = 0 ; i < q ; i++){
ll d;
cin >> d;
ops.pb(d);
}
ll o = 0;
buildSeg();
for(auto el : a){
if(el[0] == el[1]) o += (1ll * el[0]);
else if(el[0] < el[1]){
ll inx = bsSeg(1 , el[0] , el[1] - 1);
ll 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]){
ll inx = bsSeg(1 , el[1] , el[0] - 1);
ll d = 0;
if(inx < q) d = cntSeg(inx , q - 1 , 1 , el[0]);
if((d & 1)) o += (1ll * el[1]);
else o += (1ll * el[0]);
}
}
cout << o;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
11864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
11864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
11864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
