제출 #317582

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
317582		bin1st090104	운세 보기 2 (JOI14_fortune_telling2)	C++11	100 / 100	350 ms	9916 KiB

fortune_telling2

#include <bits/stdc++.h>

#define Size(x) ((int)(x).size())
#define endl '\n'

using namespace std;

template<typename T> using vc=vector<T>;
template<typename T> using vc1=vc<T>;
template<typename T> using vc2=vc<vc1<T>>;
template<typename T> using vc3=vc<vc2<T>>;
template<typename T> using vc4=vc<vc3<T>>;
template<typename T> using cr=const T&;
using pii=pair<int,int>;
using lli=long long int;
using pli=pair<lli,int>;

template<typename X,typename Y>
bool minimize(X&x,cr<Y>y){
	return (y<x?x=y,true:false);
}

template<typename X,typename Y>
bool maximize(X&x,cr<Y>y){
	return (y>x?x=y,true:false);
}

const int maxN=2e5;
const int maxM=2e5;
const int inf=0x3f3f3f3f;
const lli INF=0x3f3f3f3f3f3f3f3f;

struct Interval_Tree_Sum{
	vc<int> Node;
	int N;
	Interval_Tree_Sum(int __N){
		N=__N;
		Node.resize(4*N+3,0);
		return ;
	}
	void Upd(int i,int l,int r,int p,int v){
		if(p<l||r<p)
			return;
		if(l==r){
			Node[i]=v;
			return ;
		}
		int m=(l+r)>>1;
		if(p<=m)
			Upd(i<<1,l,m,p,v);
		else
			Upd(i<<1|1,m+1,r,p,v);
		Node[i]=Node[i<<1]+Node[i<<1|1];
		return ;
	}
	void Upd(int p,int v){
		Upd(1,1,N,p,v);
	}
	int Get(int i,int l,int r,int u,int v){
		if(v<l||r<u||u>v)
			return 0;
		if(u<=l&&r<=v)
			return Node[i];
		int m=(l+r)>>1;
		return Get(i<<1,l,m,u,v)+Get(i<<1|1,m+1,r,u,v);
	}
	int Get(int u,int v){
		return Get(1,1,N,u,v);
	}
};

struct Interval_Tree_Max{
	vc<int> Node;
	int N;
	Interval_Tree_Max(int __N){
		N=__N;
		Node.resize(4*N+3);
	}
	void Upd(int i,int l,int r,int p,int v){
		if(p<l||r<p)
			return ;
		if(l==r){
			Node[i]=v;
			return ;
		}
		int m=(l+r)>>1;
		if(p<=m)
			Upd(i<<1,l,m,p,v);
		else
			Upd(i<<1|1,m+1,r,p,v);
		Node[i]=max(Node[i<<1],Node[i<<1|1]);
		return ;
	}
	void Upd(int p,int v){
		Upd(1,1,N,p,v);
		return ;
	}
	int Get(int i,int l,int r,int u,int v){
		if(v<l||r<u||u>v)
			return -1;
		if(u<=l&&r<=v)
			return Node[i];
		int m=(l+r)>>1;
		return max(Get(i<<1,l,m,u,v),Get(i<<1|1,m+1,r,u,v));
	}
	int Get(int u,int v){
		return Get(1,1,N,u,v);
	}
};

int N,K;
pii a[maxN+3];
pii t[maxN+3];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(nullptr);
	//freopen("t.inp","r",stdin);freopen("t.out","w",stdout);
	cin>>N>>K;
	for(int i=1;i<=N;i++)
		cin>>a[i].first>>a[i].second;
	sort(a+1,a+N+1,[]
		(cr<pii>x,cr<pii>y){
			return max(x.first,x.second)>max(y.first,y.second);
		});
	for(int i=1;i<=K;i++){
		cin>>t[i].first;
		t[i].second=i;
	}
	sort(t+1,t+K+1,[]
		(cr<pii>x,cr<pii>y){
			return x.first<y.first;
	});
	Interval_Tree_Sum ITS(K);
	Interval_Tree_Max ITM(K);
	for(int i=1;i<=K;i++)
		ITM.Upd(i,t[i].second);
	lli res=0;
	int pos=K;
	for(int i=1;i<=N;i++){
		while(pos&&t[pos].first>=max(a[i].first,a[i].second)){
			ITS.Upd(t[pos].second,1);
			pos--;
		}
		int l=lower_bound(t+1,t+K+1,pii(min(a[i].first,a[i].second),-1))-t;
		int r=lower_bound(t+1,t+K+1,pii(max(a[i].first,a[i].second),-1))-t-1;
		if(l<=r){
			int maxpos=ITM.Get(l,r);
			int d=ITS.Get(maxpos+1,K);
			if(d&1)
				res+=min(a[i].first,a[i].second);
			else
				res+=max(a[i].first,a[i].second);
		}
		else{
			int d=ITS.Get(1,K);
			if(d&1)
				res+=a[i].second;
			else
				res+=a[i].first;
		}
	}
	cout<<res;
	return 0;
}

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