This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
int n,q;
int a[200007],b[200007],bit[200007],it[800007],res[200007];
long long ans=0;
vector < pair <int,int> > query,qr[200007];
int read(){
int x;
scanf("%d",&x);
return x;
}
void upd(int pos){
for(int i=pos;i<=q;i+=i&-i){
bit[i]++;
}
}
long long get(int pos){
long long res=0;
for(int i=pos;i>=1;i-=i&-i){
res+=bit[i];
}
return res;
}
void init(int k,int l,int r){
if(l==r){
it[k]=query[l-1].se;
return;
}
int mid=(l+r)/2;
init(k*2,l,mid);
init(k*2+1,mid+1,r);
it[k]=max(it[k*2],it[k*2+1]);
}
int get(int k,int l,int r,int L,int R){
if(l>R || r<L || l>r) return 0;
if(l>=L && r<=R){
return it[k];
}
int mid=(l+r)/2;
return max(get(k*2,l,mid,L,R),get(k*2+1,mid+1,r,L,R));
}
int main(){
n=read();
q=read();
for(int i=1;i<=n;i++){
a[i]=read();
b[i]=read();
}
for(int i=1;i<=q;i++){
int val=read();
query.pb(mp(val,i));
}
sort(query.begin(),query.end());
init(1,1,q);
for(int i=1;i<=n;i++){
int mi=min(a[i],b[i]);
int mx=max(a[i],b[i]);
int lef=lower_bound(query.begin(),query.end(),mp(mi,0))-query.begin();
int rig=lower_bound(query.begin(),query.end(),mp(mx,0))-query.begin()-1;
lef++;
rig++;
//cout<<lef<<" "<<rig<<" "<<get(1,1,q,lef,rig)<<endl;
if(lef<=rig){
qr[rig+1].pb(mp(i,get(1,1,q,lef,rig)));
if(a[i]<b[i]) swap(a[i],b[i]);
}
else{
qr[rig+1].pb(mp(i,1));
}
}
for(int i=q;i>=1;i--){
upd(query[i-1].se);
for(int j=0;j<(int)qr[i].size();j++){
int x=qr[i][j].fi;
res[x]=(get(q)-get(qr[i][j].se-1))%2;
}
}
for(int i=1;i<=n;i++){
if(res[i]==0) ans+=a[i];
else ans+=b[i];
}
printf("%lld",ans);
}
Compilation message (stderr)
fortune_telling2.cpp:1:0: warning: ignoring #pragma comment [-Wunknown-pragmas]
#pragma comment(linker, "/stack:200000000")
^
fortune_telling2.cpp: In function 'int read()':
fortune_telling2.cpp:16:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |