Submission #550779

#TimeUsernameProblemLanguageResultExecution timeMemory
550779codr0Fortune Telling 2 (JOI14_fortune_telling2)C++14
0 / 100
1 ms468 KiB
// Code by Parsa Eslami #include <bits/stdc++.h> #define pii pair<int,int> #define bit(i,j) ((j>>i)&1) #define FOR(i,a,b) for(int i=a;i<=b;i++) #define FORR(i,a,b) for(int i=a;i>=b;i--) #define S second #define F first #define pb push_back #define SZ(x) (int)x.size() #define all(x) x.begin(),x.end() #define err(x) cout<<#x<<": "<<x<<'\n'; using namespace std; const int N=2e5+4; const int lg=20; pii a[N]; pii b[N]; int mx[lg][N],n,k; int pw[lg]; long long ans; struct fenwick{ int fen[N]; void add(int k){ while(k<N){ fen[k]++; k+=(k&(-k)); } } int get(int k){ int rt=0; while(k>0){ rt+=fen[k]; k-=(k&(-k)); } return rt; } };fenwick fen; bool cmp(pii a,pii b){ return (max(a.F,a.S)<max(b.F,b.S)); } int MX(int l,int r){ int LG=31-__builtin_clz(r-l+1); return max(mx[LG][l],mx[LG][r-pw[LG]+1]); } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); pw[0]=1; FOR(i,1,lg-1) pw[i]=pw[i-1]*2; cin>>n>>k; FOR(i,1,n) cin>>a[i].F>>a[i].S; sort(a+1,a+1+n,cmp); FOR(i,1,k){ cin>>b[i].F; b[i].S=i;} sort(b+1,b+1+k); FOR(i,1,k) mx[0][i]=b[i].S; FOR(j,1,lg-1) FOR(i,1,k-pw[j]+1){ mx[j][i]=max(mx[j-1][i],mx[j-1][i+pw[j-1]]); } int p=k; FORR(i,n,1){ if(a[i].F==a[i].S){ ans+=a[i].F; continue; } int mx=max(a[i].F,a[i].S); int mn=a[i].F+a[i].S-mx; while(p>0&&b[p].F>=mx){ fen.add(b[p].S); p--; } int l=0,r=k+1; int R,L; while(r-l>1){ int mid=(r+l)/2; if(b[mid].F<mx) l=mid; else r=mid; } R=l; l=0,r=k+1; while(r-l>1){ int mid=(r+l)/2; if(b[mid].F>=mn) r=mid; else l=mid; } L=r; int x; if(L>R) x=-1; else x=MX(L,R); if(x==-1){ if(fen.get(n)&1) ans+=a[i].S; else ans+=a[i].F; }else{ if((fen.get(n)-fen.get(x))&1) ans+=mn; else ans+=mx; } } cout<<ans<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...