Submission #15532

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15532	2015-07-12T08:55:38 Z	comet	허수아비 (JOI14_scarecrows)	C++	100 / 100	1531 ms	30620 KB

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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	21380 KB	Output is correct
2	Correct	0 ms	21380 KB	Output is correct
3	Correct	0 ms	21380 KB	Output is correct
4	Correct	0 ms	21380 KB	Output is correct
5	Correct	0 ms	21380 KB	Output is correct
6	Correct	0 ms	21380 KB	Output is correct
7	Correct	0 ms	21380 KB	Output is correct
8	Correct	0 ms	21380 KB	Output is correct
9	Correct	0 ms	21380 KB	Output is correct
10	Correct	0 ms	21380 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	21512 KB	Output is correct
2	Correct	19 ms	21512 KB	Output is correct
3	Correct	12 ms	21512 KB	Output is correct
4	Correct	10 ms	21380 KB	Output is correct
5	Correct	11 ms	21512 KB	Output is correct
6	Correct	17 ms	21512 KB	Output is correct
7	Correct	18 ms	21512 KB	Output is correct
8	Correct	10 ms	21380 KB	Output is correct
9	Correct	17 ms	21512 KB	Output is correct
10	Correct	19 ms	21512 KB	Output is correct
11	Correct	17 ms	21512 KB	Output is correct
12	Correct	11 ms	21380 KB	Output is correct

Subtask #3

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	614 ms	30620 KB	Output is correct
2	Correct	1527 ms	29300 KB	Output is correct
3	Correct	670 ms	29300 KB	Output is correct
4	Correct	502 ms	26000 KB	Output is correct
5	Correct	783 ms	28640 KB	Output is correct
6	Correct	1066 ms	29036 KB	Output is correct
7	Correct	1301 ms	29168 KB	Output is correct
8	Correct	1502 ms	29168 KB	Output is correct
9	Correct	548 ms	26000 KB	Output is correct
10	Correct	1170 ms	29828 KB	Output is correct
11	Correct	1400 ms	29300 KB	Output is correct
12	Correct	1511 ms	29300 KB	Output is correct
13	Correct	1525 ms	29300 KB	Output is correct
14	Correct	511 ms	26000 KB	Output is correct
15	Correct	1410 ms	29300 KB	Output is correct
16	Correct	1531 ms	29300 KB	Output is correct
17	Correct	725 ms	26396 KB	Output is correct
18	Correct	1288 ms	27584 KB	Output is correct
19	Correct	1181 ms	26792 KB	Output is correct
20	Correct	1156 ms	26528 KB	Output is correct