Submission #3291

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3291	2013-08-30T10:29:22 Z	ainta	두 섬간의 연결 (kriii1_2)	C++	1 / 1	128 ms	5828 KB

2

#include<stdio.h>
#include<algorithm>
#include<set>
using namespace std;
set<int>Set;
set<int>::iterator it,it2,it3;
int n,T;
long long Res,Res2;
long long F(long long a){
	return a*(a-1)/2LL;
}
long long FF(long long a){
	return a*(a-1)*(a+1)/6LL;
}
int main()
{
	int a,b,i;
	scanf("%d",&n);
	T=n-1;
	for(i=1;i<=n;i++)Set.insert(i);
	while(T--){
		scanf("%d",&a);
		a++;
		it=Set.lower_bound(a);
		it3=it;
		it2=it;
		it3++;
		it--;
		if(it3==Set.end())b=n-(*it2)+1;
		else b=(*it3)-(*it2);
		a=(*it2)-(*it);
		Set.erase(it2);
		Res=Res-F(a)-F(b)+F(a+b);
		Res2=Res2-FF(a)-FF(b)+FF(a+b);
		printf("%lld %lld\n",Res,Res2);
	}
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	5828 KB	Output is correct
2	Correct	116 ms	5828 KB	Output is correct
3	Correct	128 ms	5828 KB	Output is correct
4	Correct	116 ms	5828 KB	Output is correct
5	Correct	80 ms	5828 KB	Output is correct
6	Correct	92 ms	5828 KB	Output is correct