oj.uz

Submission #3307

# Submission time Handle Problem Language Result Execution time Memory
3307 2013-08-30T11:24:53 Z movie_jo 두 섬간의 연결 (kriii1_2) C
1 / 1
 52 ms 3432 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3432 KB Output is correct
2 Correct 36 ms 3432 KB Output is correct
3 Correct 32 ms 3432 KB Output is correct
4 Correct 52 ms 3432 KB Output is correct
5 Correct 36 ms 3432 KB Output is correct
6 Correct 48 ms 3432 KB Output is correct