#include<bits/stdc++.h>
using namespace std;
#define int long long
int ft[10000005];
int n;
int ls(int x){
return (x&(-x));
}
int qry2(int p){
p++;
int sum = 0;
for(;p;p-=ls(p)) sum+=ft[p];
return sum;
}
void upd(int p ,int v){
p++;
for(;p<=n+1;p+=ls(p)) ft[p] += v;
}
struct node{
int s,e,m;
int val = 0;
int lazy = 0;
node *l , *r ;
node(int S,int E){
s = S, e = E, m = (s+e)/2;
if(s!=e){
l = new node(s,m);
r = new node(m+1,e);
}
}
void propogate(){
if(lazy == 0) return;
val = lazy;
if(s!=e){
l->lazy = lazy;
r->lazy = lazy;
}
lazy = 0;
}
void update(int i,int j, int k){
if(i==s && j==e) lazy = k;
else{
if(j<=m) l->update(i,j,k);
else if(i>m) r->update(i,j,k);
else l->update(i,m,k), r->update(m+1,j,k);
l->propogate(), r->propogate();
val = max(l->val,r->val);
}
}
int query(int a,int b){
if(a>e || b<s) return -1e9;
propogate();
if(a==s && b==e ) return val;
else{
if(b<=m) return l-> query(a,b);
else if(a>m) return r->query(a,b);
else return max(l->query(a,m),r->query(m+1,b));
}
}
}*root;
main(){
n = 1e7 ;
root = new node(0,n);
int N,Q;
cin>>N>>Q;
map<int,int> mp,mp2;
int left[N+3],right[N+3],qry[N+3];
bool flip[N+3];
set<int>s;
memset(flip,0,sizeof(flip));
for(int i=0;i<N;i++){
cin>>left[i]>>right[i];
s.insert(left[i]);
s.insert(right[i]);
if(left[i]>right[i]){
flip[i] = 1;
swap(left[i],right[i]);
}
}
int cnt = 1;
for(int x:s){
mp[x] = cnt;
mp2[cnt] = x;
cnt++;
}
for(int i=0;i<N;i++){
left[i] = mp[left[i]];
right[i] = mp[right[i]];
}
for(int i=0;i<Q;i++){
cin>>qry[i];
auto it = mp.upper_bound(qry[i]);
if(it == mp.begin()) qry[i] = 0;
else{
it--;
qry[i] = it->second;
}
root->update(qry[i],qry[i],i+1);
}
priority_queue<pair<int,int> >pq;
for(int i=0;i<N;i++){
int x = root->query(left[i],right[i]-1);
pq.push(make_pair(x,i));
}
assert(1==0);
int ans = 0;
for(int i=Q-1;i>=0;i--){
while(!pq.empty() && pq.top().first-1 == i){
int y = qry2(n) - qry2(right[pq.top().second]-1);
if((y%2==0 && flip[pq.top().second] == 0) || (y%2==1 && flip[pq.top().second] == 1)){
ans+=mp2[left[pq.top().second]];
}
else ans+=mp2[right[pq.top().second]];
pq.pop();
}
upd(qry[i],1);
}
while(!pq.empty()){
//cout<<pq.top().second;
int y = qry2(n) - qry2(right[pq.top().second]-1);
if((y%2==0 && flip[pq.top().second] == 0) || (y%2==1 && flip[pq.top().second] == 1)){
ans+=mp2[left[pq.top().second]];
}
else ans+=mp2[right[pq.top().second]];
pq.pop();
}
cout<<ans;
}
Compilation message
fortune_telling2.cpp:65:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
65 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
176 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
176 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
176 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
