oj.uz

답안 #3291

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
3291 2013-08-30T10:29:22 Z ainta 두 섬간의 연결 (kriii1_2) C++
1 / 1
 128 ms 5828 KB 
#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

# 결과 실행 시간 메모리 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