제출 #15532

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
15532		comet	허수아비 (JOI14_scarecrows)	C++98	100 / 100	1531 ms	30620 KiB

scarecrows

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
ll n,a[200010],lu[200010],x[200010],y[200010];
int st[200010][17];
ll f(int L,int R){
	if(L==R)return 0;
	ll ret=0;
	int mid=(L+R)/2;
	ret+=f(L,mid)+f(mid+1,R);
	map<int,int> LL;
	set<int> RR;
	map<int,int>::iterator it;
	set<int>::iterator jt;
	LL[-1]=-1,LL[a[mid]]=mid;
	for(int i=0;i<17;i++)st[mid][i]=-1;
	for(int i=mid-1;i>=L;i--){
		it=LL.lower_bound(a[i]);
		it--;
		st[i][0]=it->second;
		for(int j=1;j<17;j++){
			if(st[i][j-1]>=0)st[i][j]=st[st[i][j-1]][j-1];
			else st[i][j]=-1;
		}
		LL[a[i]]=i;
	}
	RR.insert(-1);
	for(int i=mid+1;i<=R;i++){
		jt=RR.lower_bound(a[i]);
		jt--;
		it=LL.lower_bound(a[i]);
		it--;
		int p=it->second;
		int t=0;
		if(p<0||a[p]<=*jt)continue;
		ret++;
		for(int j=16;j>=0;j--)
			if(!(st[p][j]<0||a[st[p][j]]<*jt))
				p=st[p][j],ret+=(1ll<<j);
		ret+=t;
		RR.insert(a[i]);
	}
	return ret;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>x[i]>>y[i];
		lu[i]=x[i];
	}
	sort(lu,lu+n);
	for(int i=0;i<n;i++)a[lower_bound(lu,lu+n,x[i])-lu]=y[i];
	for(int i=0;i<n;i++)lu[i]=a[i];
	sort(lu,lu+n);
	for(int i=0;i<n;i++)a[i]=lower_bound(lu,lu+n,a[i])-lu;
	cout<<f(0,n-1);
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 85 / 85