Submission #516523

#	Time	Username	Problem	Language	Result	Execution time	Memory
516523		MilosMilutinovic	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	35 / 100	205 ms	100592 KiB

fortune_telling2

#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}

ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,m,q;
int a[200005],b[200005],x[200005];

namespace cpr{
	vector<int> v;
	void add(int x){ v.pb(x); }
	void build(){
		sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());
	}
	int get(int x){
		return lower_bound(v.begin(),v.end(),x)-v.begin();
	}
};

namespace sgt1{
	int maxa[400005];
	void change(int id,int l,int r,int qi,int c){
		if(l==r) return (void)(maxa[id]=max(maxa[id],c));
		int mid=(l+r)/2;
		if(qi<=mid) change(id<<1,l,mid,qi,c);
		else change(id<<1|1,mid+1,r,qi,c);
		maxa[id]=max(maxa[id<<1],maxa[id<<1|1]);
	}
	int query(int id,int l,int r,int ql,int qr){
		if(ql>qr||l>qr||r<ql) return 0;
		if(ql<=l&&r<=qr) return maxa[id];
		int mid=(l+r)/2;
		return max(query(id<<1,l,mid,ql,qr),query(id<<1|1,mid+1,r,ql,qr));
	}
};

namespace psgt{
	int root[200005],lc[4000005],rc[4000005],st[4000005],tsz;
	void change(int&id,int p,int l,int r,int qi){
		id=++tsz; lc[id]=lc[p]; rc[id]=rc[p]; st[id]=st[p]+1;
		if(l==r) return;
		int mid=(l+r)/2;
		if(qi<=mid) change(lc[id],lc[p],l,mid,qi);
		else change(rc[id],rc[p],mid+1,r,qi);
	}
	int query(int id,int l,int r,int ql,int qr){
		if(l>qr||r<ql) return 0;
		if(ql<=l&&r<=qr) return st[id];
		int mid=(l+r)/2;
		return query(lc[id],l,mid,ql,qr)+query(rc[id],mid+1,r,ql,qr);
	}
	int query(int i,int l,int r){ return query(root[i],0,m-1,l,r); }
	void update(int i,int x){ change(root[i],root[i+1],0,m-1,x); }
};

int main(){
	n=readint(); q=readint();
	for(int i=1;i<=n;i++) a[i]=readint(),b[i]=readint();
	for(int i=1;i<=q;i++) x[i]=readint();
	for(int i=1;i<=n;i++) cpr::add(a[i]),cpr::add(b[i]);
	for(int i=1;i<=q;i++) cpr::add(x[i]);
	cpr::build();
	m=cpr::v.size();
	for(int i=1;i<=n;i++) a[i]=cpr::get(a[i]),b[i]=cpr::get(b[i]);
	for(int i=1;i<=q;i++) x[i]=cpr::get(x[i]);
	for(int i=1;i<=q;i++) sgt1::change(1,0,m-1,x[i],i);
	for(int i=q;i>=1;i--) psgt::update(i,x[i]);
	ll ans=0;
	for(int i=1;i<=n;i++){
		int mn=min(a[i],b[i]),mx=max(a[i],b[i]);
		int id=sgt1::query(1,0,m-1,mn,mx-1);
		int cnt=psgt::query(id+1,mx,m-1);
		if(id!=0) a[i]=mx,b[i]=mn;
		if(cnt&1) swap(a[i],b[i]);
		ans+=cpr::v[a[i]];
	}
	printf("%lld\n",ans);
	return 0;
}

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