This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define int long long
using namespace std;
int N=6e5+1;
struct segtree{
int info[2400005];
void upd(int st,int en,int i,int pos,int val){
if(st>pos||en<pos)return;
if(st==en)return void(info[i]=val);
int m=(st+en)/2;
upd(st,m,i*2,pos,val);
upd(m+1,en,i*2+1,pos,val);
info[i]=max(info[i*2],info[i*2+1]);
}
int fmax(int st,int en,int i,int l,int r){
if(st>r||en<l)return 0;
if(st>=l&&en<=r)return info[i];
int m=(st+en)/2;
return max(fmax(st,m,i*2,l,r),fmax(m+1,en,i*2+1,l,r));
}
}str;
struct fenwick{
int info[600005];
void upd(int x,int val){
for(int i=x;i<=600000;i+=(i&-i)){
info[i]+=val;
}
}
int fsum(int x){
int sum=0;
for(int i=x;i>0;i-=(i&-i)){
sum+=info[i];
}
return sum;
}
}ftr;
int ca[600005];
int cb[600005];
int cca[600005];
int ccb[600005];
vector<int>v;
vector<int>q;
vector<int>nq;
map<int,int>mp;
vector<pair<int,int> >qr[600005];
int side[600005];
int val[600005];
int ans[600005];
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>ca[i]>>cb[i];
if(!mp[ca[i]])mp[ca[i]]++,v.push_back(ca[i]);
if(!mp[cb[i]])mp[cb[i]]++,v.push_back(cb[i]);
}
for(int i=1;i<=k;i++){
int x;
cin>>x;
q.push_back(x);
if(!mp[x])mp[x]++,v.push_back(x);
}
sort(v.begin(),v.end());
for(int i=1;i<=k;i++){
int id=lower_bound(v.begin(),v.end(),q[i-1])-v.begin()+1;
//cerr<<q[i-1]<<":"<<id<<"\n";
nq.push_back(id);
str.upd(1,N,1,id,i);
//cerr<<str.fmax(1,N,1,id,id)<<":"<<id<<"\n";
}
for(int i=0;i<n;i++){
int id=lower_bound(v.begin(),v.end(),ca[i])-v.begin()+1;
cca[i]=id;
id=lower_bound(v.begin(),v.end(),cb[i])-v.begin()+1;
ccb[i]=id;
}
int sum=0;
for(int i=0;i<n;i++){
if(ca[i]<cb[i]){
int l=str.fmax(1,N,1,cca[i],ccb[i]-1);
qr[l].push_back({i,ccb[i]});
//cerr<<"L:"<<l<<" "<<ccb[i]<<"\n";
side[i]=1;
if(l==0)side[i]=0;
}else if(ca[i]>cb[i]){
int l=str.fmax(1,N,1,ccb[i],cca[i]-1);
qr[l].push_back({i,cca[i]});
//cerr<<"L:"<<l<<" "<<cca[i]<<"\n";
side[i]=0;
}else{
side[i]=0;
sum+=ca[i];
}
}
/*for(int i=0;i<n;i++){
cerr<<cca[i]<<" "<<ccb[i]<<"\n";
}
for(int i=1;i<=8;i++){
//cerr<<str.fmax(1,N,1,i,i)<<" ";
}cerr<<endl;*/
int cur=6e5;
for(int i=k;i>=1;i--){
//cerr<<i<<"?"<<nq[i-1]<<"\n";
while(cur>i){
//cerr<<"cur:"<<cur<<"\n";
for(auto x:qr[cur]){
int id=x.second;
int am=ftr.fsum(6e5)-ftr.fsum(id-1);
//cerr<<x.first<<" "<<ftr.fsum(2e5)<<"-"<<ftr.fsum(id-1)<<"\n";
if(am%2==1)side[x.first]^=1;
ans[x.first]=side[x.first];
sum+=ans[x.first]==0?ca[x.first]:cb[x.first];
//cerr<<am<<" ans"<<x.first<<" "<<(ans[x.first]==0?ca[x.first]:cb[x.first])<<"\n";
}
cur--;
}
//cerr<<"work\n";
ftr.upd(nq[i-1],1);
//cerr<<"work\n";
}
while(cur>=0){
for(auto x:qr[cur]){
int id=x.second;
int am=ftr.fsum(6e5)-ftr.fsum(id-1);
if(am%2==1)side[x.first]^=1;
ans[x.first]=side[x.first];
sum+=ans[x.first]==0?ca[x.first]:cb[x.first];
//cerr<<am<<" ans"<<x.first<<" "<<(ans[x.first]==0?ca[x.first]:cb[x.first])<<"\n";
}
cur--;
}
cout<<sum;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |