oj.uz

Submission #15525

# Submission time Handle Problem Language Result Execution time Memory
15525 2015-07-12T08:50:15 Z comet 허수아비 (JOI14_scarecrows) C++
100 / 100
 1551 ms 30620 KB 
#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;
	}
	//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=16;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
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 2 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 5 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 13 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 9 ms 21380 KB Output is correct
9 Correct 17 ms 21512 KB Output is correct
10 Correct 20 ms 21512 KB Output is correct
11 Correct 19 ms 21512 KB Output is correct
12 Correct 7 ms 21380 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 30620 KB Output is correct
2 Correct 1521 ms 29300 KB Output is correct
3 Correct 675 ms 29300 KB Output is correct
4 Correct 522 ms 26000 KB Output is correct
5 Correct 776 ms 28640 KB Output is correct
6 Correct 1053 ms 29036 KB Output is correct
7 Correct 1322 ms 29168 KB Output is correct
8 Correct 1483 ms 29168 KB Output is correct
9 Correct 533 ms 26000 KB Output is correct
10 Correct 1146 ms 29828 KB Output is correct
11 Correct 1434 ms 29300 KB Output is correct
12 Correct 1508 ms 29300 KB Output is correct
13 Correct 1551 ms 29300 KB Output is correct
14 Correct 496 ms 26000 KB Output is correct
15 Correct 1414 ms 29300 KB Output is correct
16 Correct 1533 ms 29300 KB Output is correct
17 Correct 708 ms 26396 KB Output is correct
18 Correct 1278 ms 27584 KB Output is correct
19 Correct 1181 ms 26792 KB Output is correct
20 Correct 1150 ms 26528 KB Output is correct