Submission #3313

#	Time	Username	Problem	Language	Result	Execution time	Memory
3313		mjy0503	두 섬간의 연결 (kriii1_2)	C++98	1 / 1	48 ms	2260 KiB

2

#include <stdio.h>
long long print[2],cnt[100001];
int team[100001];
long long fir(long long a){
	return a*(a-1)/2;
}
long long sec(long long a){
	return (a-1)*a*(a+1)/6;
}
int main(){
	int n,i,a,j;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		team[i]=i;
		cnt[i]=1;
	}
	for(i=0;i<n-1;i++){
		scanf("%d",&a);
		print[0]-=fir(cnt[a]);
		print[0]-=fir(cnt[team[a-1]]);
		print[1]-=sec(cnt[a]);
		print[1]-=sec(cnt[team[a-1]]);
		for(j=a;j<n;j++){
			if(team[j]!=a) break;
			team[j]=team[a-1];
			cnt[team[a-1]]++;
		}
		print[0]+=fir(cnt[team[a-1]]);
		print[1]+=sec(cnt[team[a-1]]);
		printf("%lld %lld\n",print[0],print[1]);
	}
	return 0;
}

• Subtask 1: 1 / 1