#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=2e5+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<62);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()
struct node{
ll l,r,val,ti;
node *lc,*rc;
}*rt=new node{0,MOD,0,0,0,0};
int get(node *nd){return (!nd?0:nd->val);}
void insert(node *nd,ll to,ll id){
if(nd->l==nd->r-1){nd->val=max(nd->val,id);nd->ti++;return;}
ll mid=(nd->l+nd->r)/2;
if(to>=mid){
if(!nd->rc)nd->rc=new node{mid,nd->r,0,0,0,0};
insert(nd->rc,to,id);
}else{
if(!nd->lc)nd->lc=new node{nd->l,mid,0,0,0,0};
insert(nd->lc,to,id);
}
nd->val=max(get(nd->rc),get(nd->lc));
}
void reset(node *nd){
if(nd->lc)reset(nd->lc);
if(nd->rc)reset(nd->rc);
if(nd!=rt)delete nd;
else rt->val=rt->ti=0;
}
ll ans,x[N],a[N],b[N],tt[N],lin[N],n,k;
vector<ll> v[N];
ll q(node *nd,ll ql,ll qr,ll ty){
if(!nd)return 0;
if(nd->l>=ql&&nd->r<=qr){return (ty?nd->ti:nd->val);}
if(nd->l>=qr||nd->r<=ql)return 0;
if(ty){
return q(nd->lc,ql,qr,ty)+q(nd->rc,ql,qr,ty);
}else{
return max(q(nd->lc,ql,qr,ty),q(nd->rc,ql,qr,ty));
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>k;
REP1(i,n)cin>>a[i]>>b[i];
REP1(i,k){
cin>>x[i];
insert(rt,x[i],i);
}
REP1(i,n){
ll tmp=q(rt,min(a[i],b[i]),max(a[i],b[i]),0);
v[tmp].pb(i);
lin[i]=tmp;
}
/*REP1(i,n){
cout<<i<<" "<<lin[i]<<"\n";
}*/
reset(rt);
for(ll i=k;i>=0;i--){
for(auto j:v[i]){
tt[j]=q(rt,max(a[i],b[i]),MOD,1);
}
insert(rt,x[i],i);
}
REP1(i,n){
if(lin[i]==0){
ans+=(tt[i]%2?b[i]:a[i]);
}else{
ans+=(tt[i]%2?max(a[i],b[i]):min(a[i],b[i]));
}
}
cout<<ans<<"\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
185 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
185 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
185 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
