Submission #3291

#	Time	Username	Problem	Language	Result	Execution time	Memory
3291		ainta	두 섬간의 연결 (kriii1_2)	C++98	1 / 1	128 ms	5828 KiB

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 / 1