Submission #550780

#	Time	Username	Problem	Language	Result	Execution time	Memory
550780		codr0	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	189 ms	23280 KiB

fortune_telling2

// 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(k)&1) ans+=a[i].S;
			else ans+=a[i].F;
		}else{
			if((fen.get(k)-fen.get(x))&1) ans+=mn;
			else ans+=mx;
		}
	}
	cout<<ans<<'\n';

	return 0;
	}

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65