| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 719993 | hello_there_123 | 운세 보기 2 (JOI14_fortune_telling2) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define int long long
int ft[1000000005];
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 = 1e9 ;
root = new node(0,n);
int N,Q;
cin>>N>>Q;
int left[N+3],right[N+3],qry[N+3];
bool flip[N+3];
memset(flip,0,sizeof(flip));
for(int i=0;i<N;i++){
cin>>left[i]>>right[i];
if(left[i]>right[i]){
flip[i] = 1;
swap(left[i],right[i]);
}
}
for(int i=0;i<Q;i++){
cin>>qry[i];
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));
}
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+=left[pq.top().second];
}
else ans+=right[pq.top().second];
//cout<<ans<<" "<<pq.top().second<<" "<<pq.top().first<<"\n";
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+=left[pq.top().second];
}
else ans+=right[pq.top().second];
//cout<<ans<<" "<<pq.top().second<<" "<<pq.top().first<<"\n";
pq.pop();
}
cout<<ans;
}