#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=200010, inf=2e9;
int n, m, k;
int Q[MX];
pii C[MX];
vector<int> X;
struct SEG1{
int tree[2*MX*4], n; // max seg
void init(int sz){
n=sz;
for(int i=1; i<4*sz; i++) tree[i]=0;
}
void upt(int v, int s, int e, int pos, int val){
if(pos<s || e<pos) return;
tree[v]=max(tree[v], val);
if(s==e) return;
upt(v*2, s, (s+e)/2, pos, val);
upt(v*2+1, (s+e)/2+1, e, pos, val);
}
void upt(int pos, int val){
upt(1,1,n,pos,val);
}
int mx(int v, int s, int e, int l, int r){
if(e<l || r<s) return 0;
if(l<=s && e<=r) return tree[v];
return max(mx(v*2, s, (s+e)/2, l, r), mx(v*2+1, (s+e)/2+1, e, l, r));
}
int mx(int l, int r){
return mx(1,1,n,l,r);
}
} MT;
struct SEG2{
int tree[MX], n; // sum BIT
void init(int sz){
n=sz;
for(int i=1; i<=n; i++) tree[i]=0;
}
void upt(int pos){
for(; 0<pos && pos<=n; pos+=pos&(-pos))
tree[pos]++;
}
int sum(int pos){
int ans=0;
for(; pos>0; pos-=pos&(-pos))
ans+=tree[pos];
return ans;
}
int sum(int l, int r){
return sum(r)-sum(l-1);
}
} ST;
int find(int x){
// 이하인 최대 인덱스. 0~m
return upper_bound(X.begin(), X.end(), x)-X.begin();
}
ll solve(){
int idx[MX]; ll ans=0;
iota(idx, idx+k+1, 0);
sort(idx+1, idx+k+1, [](int a, int b){
return Q[a]<Q[b];
});
ST.init(k);
MT.init(X.size());
for(int i=1, bck=k, frt=1; i<=n; i++){
int x,y; tie(x,y)=C[i];
if(x==y){ ans+=x; continue; }
if(x>y) swap(x,y);
while(bck>0 && Q[idx[bck]]>=y) ST.upt(idx[bck]), bck--;
while(frt<=k && Q[idx[frt]]<y) MT.upt(find(Q[idx[frt]]), idx[frt]), frt++;
int pos=MT.mx(find(x), find(y-1));
if(pos==0){
ans+= (ST.sum(pos+1, k)%2==1 ? C[i].second : C[i].first);
}
else{
ans+= (ST.sum(pos+1, k)%2==1 ? x : y);
}
}
return ans;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>k;
for(int i=1, a, b; i<=n; i++){
cin>>a>>b;
C[i]={a,b};
X.push_back(a);
X.push_back(b);
}
sort(X.begin(), X.end());
X.resize(unique(X.begin(), X.end())-X.begin());
for(int i=1; i<=k; i++) cin>>Q[i];
cout<<solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
