//雪花飄飄北風嘯嘯
//天地一片蒼茫
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
struct node{
int s,e,m;
int val=-1;
node *l,*r;
node (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
if (s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void update(int i,int j){
val=max(val,j);
if (s==e) return;
else if (i<=m) l->update(i,j);
else if (m<i) r->update(i,j);
}
int query(int i,int j){
if (s==i && e==j) return val;
else if (j<=m) return l->query(i,j);
else if (m<i) return r->query(i,j);
else return max(l->query(i,m),r->query(m+1,j));
}
} *root=new node(0,600005);
struct node2{
int s,e,m;
int val=0;
node2 *l,*r;
node2 (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
if (s!=e){
l=new node2(s,m);
r=new node2(m+1,e);
}
}
void update(int i){
val++;
if (s==e) return;
else if (i<=m) l->update(i);
else if (m<i) r->update(i);
}
int query(int i,int j){
if (s==i && e==j) return val;
else if (j<=m) return l->query(i,j);
else if (m<i) return r->query(i,j);
else return l->query(i,m)+r->query(m+1,j);
}
} *root2=new node2(0,600005);
int n,q;
ii arr[200005];
int brr[200005];
vector<ii> proc;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
cin>>n>>q;
rep(x,0,n) cin>>arr[x].fi>>arr[x].se;
rep(x,0,q) cin>>brr[x];
vector<int> uni;
rep(x,0,n) uni.push_back(arr[x].fi),uni.push_back(arr[x].se);
rep(x,0,q) uni.push_back(brr[x]);
sort(all(uni));
uni.erase(unique(all(uni)),uni.end());
map<int,int> id;
rep(x,0,sz(uni)) id[uni[x]]=x;
rep(x,0,n) arr[x].fi=id[arr[x].fi],arr[x].se=id[arr[x].se];
rep(x,0,q) brr[x]=id[brr[x]];
rep(x,0,q){
root->update(brr[x],x);
}
rep(x,0,n){
ii temp=arr[x];
if (temp.fi>temp.se) swap(temp.fi,temp.se);
int val=-1;
if (temp.fi!=temp.se) val=root->query(temp.fi,temp.se-1);
proc.push_back(ii(val+1,x));
}
sort(all(proc));
int idx=n;
ll ans=0;
while (!proc.empty()){
while (idx!=proc.back().fi){
idx--;
root2->update(brr[idx]);
}
int pos=proc.back().se;
bool orient;
if (proc.back().fi==0) orient=false;
else orient=arr[pos].fi<arr[pos].se;
orient^=(root2->query(max(arr[pos].fi,arr[pos].se),600005))%2;
//cout<<pos<<" "<<orient<<endl;
if (!orient) ans+=uni[arr[pos].fi];
else ans+=uni[arr[pos].se];
proc.pop_back();
}
cout<<ans<<endl;
}
Compilation message
fortune_telling2.cpp: In constructor 'node::node(int, int)':
fortune_telling2.cpp:34:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
34 | s=_s,e=_e,m=s+e>>1;
| ~^~
fortune_telling2.cpp: In constructor 'node2::node2(int, int)':
fortune_telling2.cpp:64:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
64 | s=_s,e=_e,m=s+e>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
271 ms |
229100 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
271 ms |
229100 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
271 ms |
229100 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
