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>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
using pii=pair<int,int>;
using pli=pair<long long,int>;
using pil=pair<int,long long>;
using pll=pair<long long,long long>;
const int maxn=2e5+9;
int st[maxn*4*3];
void update(int id,int l,int r,int u,int val){
if (l>u||r<u)return;
if (l==r){
st[id]=val;
return;
}
int mid=(l+r)/2;
update(id*2,l,mid,u,val);
update(id*2+1,mid+1,r,u,val);
st[id]=max(st[id*2],st[id*2+1]);
}
int get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return 0;
if (u<=l&&r<=v)return st[id];
int mid=(l+r)/2;
return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
int m;
int bit[maxn*3];
void add(int pos,int val){
for(;pos<=m;pos+=(pos-(pos&(pos-1))))bit[pos]+=val;
}
int get(int pos){
if (pos==0)return 0;
int sum=0;
for(;pos>=1;pos-=(pos-(pos&(pos-1))))sum+=bit[pos];
return sum;
}
int a[maxn*3],b[maxn*3];
int c[maxn*3];
bool flip[maxn*3];
int d[maxn*3];
int ren[maxn*3];
vector<int>query[maxn*3];
signed main(){
srand(time(0));
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("usaco.INP","r",stdin);
//freopen("usaco.OUT","w",stdout);
int n,q;
cin>>n>>q;
vector<int>num;
num.pb(0);
for1(i,1,n){
cin>>a[i]>>b[i];
num.pb(a[i]);
num.pb(b[i]);
}
for1(i,1,q){
cin>>c[i];
num.pb(c[i]);
}
sort(all(num));
map<int,int>nen;
m=0;
for1(i,1,sz(num)-1){
if (num[i]>num[i-1]){
nen[num[i]]=nen[num[i-1]]+1;
m=nen[num[i]];
ren[m]=num[i];
}
}
for1(i,1,n){
a[i]=nen[a[i]];
b[i]=nen[b[i]];
}
for1(i,1,q)c[i]=nen[c[i]];
for1(i,1,q){
update(1,1,m,c[i],i);
}
for1(i,1,n){
int x=min(a[i],b[i]),y=max(a[i],b[i]);
int vcl=get(1,1,m,x,y-1);
if (vcl==0){
continue;
}
query[vcl].pb(i);
if (a[i]<b[i]){
flip[i]=1;
}
}
for1(i,1,q){
add(c[i],1);
for (auto v:query[i]){
d[v]=-get(m)+get(max(a[v],b[v])-1);
}
}
long long sum=0;
for1(i,1,n){
d[i]+=get(m)-get(max(a[i],b[i])-1);
d[i]%=2;
flip[i]^=d[i];
if (!flip[i]){
sum+=ren[a[i]];
}
else sum+=ren[b[i]];
}
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... |