#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
ll readint(){
ll x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,m,q;
int a[200005],b[200005],x[200005];
namespace cpr{
vector<int> v;
void add(int x){ v.pb(x); }
void build(){
sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());
}
int get(int x){
return lower_bound(v.begin(),v.end(),x)-v.begin();
}
};
namespace sgt1{
int maxa[400005];
void change(int id,int l,int r,int qi,int c){
if(l==r) return (void)(maxa[id]=max(maxa[id],c));
int mid=(l+r)/2;
if(qi<=mid) change(id<<1,l,mid,qi,c);
else change(id<<1|1,mid+1,r,qi,c);
maxa[id]=max(maxa[id<<1],maxa[id<<1|1]);
}
int query(int id,int l,int r,int ql,int qr){
if(l>qr||r<ql) return 0;
if(ql<=l&&r<=qr) return maxa[id];
int mid=(l+r)/2;
return max(query(id<<1,l,mid,ql,qr),query(id<<1|1,mid+1,r,ql,qr));
}
};
namespace psgt{
int root[200005],lc[4000005],rc[4000005],st[4000005],tsz;
void change(int&id,int p,int l,int r,int qi){
id=++tsz; lc[id]=lc[p]; rc[id]=rc[p]; st[id]=st[p]+1;
if(l==r) return;
int mid=(l+r)/2;
if(qi<=mid) change(lc[id],lc[p],l,mid,qi);
else change(rc[id],rc[p],mid+1,r,qi);
}
int query(int id,int l,int r,int ql,int qr){
if(l>qr||r<ql) return 0;
if(ql<=l&&r<=qr) return st[id];
int mid=(l+r)/2;
return query(lc[id],l,mid,ql,qr)+query(rc[id],mid+1,r,ql,qr);
}
int query(int i,int l,int r){ return query(root[i],0,m-1,l,r); }
void update(int i,int x){ change(root[i],root[i+1],0,m-1,x); }
};
int main(){
n=readint(); q=readint();
for(int i=1;i<=n;i++) a[i]=readint(),b[i]=readint();
for(int i=1;i<=q;i++) x[i]=readint();
for(int i=1;i<=n;i++) cpr::add(a[i]),cpr::add(b[i]);
for(int i=1;i<=q;i++) cpr::add(x[i]);
cpr::build();
m=cpr::v.size();
for(int i=1;i<=n;i++) a[i]=cpr::get(a[i]),b[i]=cpr::get(b[i]);
for(int i=1;i<=q;i++) x[i]=cpr::get(x[i]);
for(int i=1;i<=q;i++) sgt1::change(1,0,m-1,x[i],i);
for(int i=q;i>=1;i--) psgt::update(i,x[i]);
ll ans=0;
for(int i=1;i<=n;i++){
int mn=min(a[i],b[i]),mx=max(a[i],b[i]);
int id=sgt1::query(1,0,m-1,mn,mx-1);
int cnt=psgt::query(id,mx,m-1);
if(id!=0) a[i]=mx,b[i]=mn;
if(cnt&1) swap(a[i],b[i]);
ans+=cpr::v[a[i]];
}
printf("%lld\n",ans);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
440 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
476 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
440 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
476 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
440 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
476 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
