Submission #15518

#	Time	Username	Problem	Language	Result	Execution time	Memory
15518		comet	허수아비 (JOI14_scarecrows)	C++98	0 / 100	66 ms	11748 KiB

scarecrows

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
ll n,a[100010],lu[100010],x[100010],y[100010];
int st[100010][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<5;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;
	}
	//cout<<"L="<<L<<" R="<<R<<endl<<"ST = ";
	//for(int i=L;i<=mid;i++)cout<<st[i][0]<<" ";
	//cout<<endl;
	RR.insert(-1);
	for(int i=mid+1;i<=R;i++){
		//printf("i=%d: ",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;
		//cout<<"hi="<<a[i]<<", lo="<<*jt<<endl;
		ret++;
		for(int j=5;j>=0;j--){
			if(!(st[p][j]<0||a[st[p][j]]<*jt))p=st[p][j],ret+=(1ll<<j);
			//printf("(%d) %d:%d/ ",j,p,(st[p][j]<0?-1:a[st[p][j]]));
		}
		//puts("");
		ret+=t;
		RR.insert(a[i]);
	}
	//cout<<endl<<"ret="<<ret<<endl;
	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;
	//for(int i=0;i<n;i++)cout<<a[i]<<" ";
	//cout<<endl;
	cout<<f(0,n-1);
}

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