Submission #3307

#	Time	Username	Problem	Language	Result	Execution time	Memory
3307		movie_jo	두 섬간의 연결 (kriii1_2)	C11	1 / 1	52 ms	3432 KiB

2

#include <stdio.h>

struct SUM {
	int f;
	int l;
	struct SUM *bef;
	struct SUM *aft;
} s[100001];

int main(void)
{
	int N, I, i;
	long long A = 0, B = 0, a, b, x, y;

	scanf("%d", &N);

	for(i = 1; i < N; i++)
	{
		s[i].f = i;
		s[i].l = i;
		s[i].aft = &s[i + 1];
		s[i + 1].bef = &s[i];
	}

	s[N].f = N;
	s[N].l = N;

	while(--N)
	{
		scanf("%d", &I);

		x = s[I].l - s[I].f + 1;
		y = s[I].aft->l - s[I].aft->f + 1;

		a = x*(x - 1)/2;
		b = y*(y - 1)/2;

		A += x*y;
		B += x*b + y*a + x*y;

		s[I].aft->f = s[I].f;
		s[I].aft->bef = s[I].bef;

		if(s[I].bef != NULL)
			s[I].bef->aft = s[I].aft;

		printf("%lld %lld\n", A, B);
	}

	return 0;
}

• Subtask 1: 1 / 1