#include <bits/stdc++.h>
using namespace std;
const int SIZE = 1<<19;
struct ST{
int data[2*SIZE];
void update(int x, int v){
for(x+=SIZE; x; x>>=1) data[x] = max(data[x], v);
}
int query(int s, int e){
int ret = 0;
for(s+=SIZE, e+=SIZE; s<=e; s>>=1, e>>=1){
if( s&1) ret = max(ret, data[s++]);
if(~e&1) ret = max(ret, data[e--]);
}
return ret;
}
} seg;
struct PST{
struct Node{
int l,r;
bool v;
} node[20*SIZE];
int cnt;
int init(int s, int e){
int nn = cnt++;
if(s==e) return nn;
int m = s+e>>1;
node[nn].l = init(s, m), node[nn].r = init(m+1, e);
return nn;
}
int update(int bef, int ns, int ne, int x){
if(ns>x || ne<x) return bef;
int nn = cnt++;
auto &cur = node[nn];
if(ns==ne){
cur = node[bef];
cur.v ^= 1;
return nn;
}
int m = ns+ne>>1;
cur.l = update(node[bef].l, ns, m, x), cur.r = update(node[bef].r, m+1, ne, x);
cur.v = node[cur.l].v ^ node[cur.r].v;
return nn;
}
bool query(int nn, int ns, int ne, int s, int e){
if(ns>e || ne<s) return 0;
auto &cur = node[nn];
if(s<=ns && ne<=e) return cur.v;
int m = ns+ne>>1;
return query(cur.l, ns, m, s, e) ^ query(cur.r, m+1, ne, s, e);
}
} pst;
int root[200001], A[200001], B[200001], T[200001];
vector<int> xx;
int main(){
ios_base::sync_with_stdio(0), cin.tie(0);
int N, K; cin>>N>>K;
for(int i=0; i<N; ++i) cin>>A[i]>>B[i], xx.push_back(A[i]), xx.push_back(B[i]);
for(int i=1; i<=K; ++i) cin>>T[i];
sort(xx.begin(), xx.end()), xx.erase(unique(xx.begin(), xx.end()), xx.end());
for(int i=0; i<N; ++i){
A[i] = lower_bound(xx.begin(), xx.end(), A[i]) - xx.begin() + 1;
B[i] = lower_bound(xx.begin(), xx.end(), B[i]) - xx.begin() + 1;
}
root[K+1] = pst.init(0, xx.size());
for(int i=K; i; --i){
T[i] = upper_bound(xx.begin(), xx.end(), T[i]) - xx.begin();
seg.update(T[i], i);
root[i] = pst.update(root[i+1], 0, xx.size(), T[i]);
}
long long ans = 0;
for(int i=0; i<N; ++i){
int a=A[i], b=B[i];
if(a>b) swap(a, b);
int t = seg.query(a, b-1), s = pst.query(root[t], 0, xx.size(), b, xx.size());
if(t && s) ans += xx[a-1];
else if(t) ans += xx[b-1];
else if(s) ans += xx[B[i]-1];
else ans += xx[A[i]-1];
}
cout<<ans<<'\n';
return 0;
}
Compilation message
fortune_telling2.cpp: In member function 'int PST::init(int, int)':
fortune_telling2.cpp:28:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e>>1;
~^~
fortune_telling2.cpp: In member function 'int PST::update(int, int, int, int)':
fortune_telling2.cpp:41:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = ns+ne>>1;
~~^~~
fortune_telling2.cpp: In member function 'bool PST::query(int, int, int, int, int)':
fortune_telling2.cpp:50:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = ns+ne>>1;
~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
512 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
640 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
512 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
640 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
512 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
640 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
