Submission #20204

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
20204	2016-03-27T13:38:46 Z	kipa00	컬러볼 (KOI15_ball)	C++	25 / 25	140 ms	40 KB

ball

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX = 200001;

pair<int, pair<int, int> > datas[MAX];
unsigned int sum[MAX], partial_sum[MAX], lastsum[MAX];
int lasts[MAX], lastsi[MAX];

int main() {
	int i, n, last = -1;
	scanf("%d", &n);
	for (i=0; i<n; ++i) {
		scanf("%d%d", &datas[i].second.first, &datas[i].first);
		datas[i].second.second = i;
		lasts[i] = -1;
	}
	stable_sort(datas, datas + n);
	for (i=0; i<n; ++i) {
		if (i) {
			sum[i] = sum[i - 1] + datas[i - 1].first;
			partial_sum[i] = lastsum[datas[i].second.first];
			lastsum[datas[i].second.first] = lastsum[datas[i].second.first] + datas[i].first;
		} else {
			lastsum[datas[0].second.first] = datas[0].first;
		}
	}
	for (i=0; i<n; ++i) {
		if (last == datas[i].first) {
			sum[i] = sum[i - 1];
		} else {
			last = datas[i].first;
		}
		if (lasts[datas[i].second.first] == datas[i].first) {
			partial_sum[i] = partial_sum[lastsi[datas[i].second.first]];
		} else {
			lasts[datas[i].second.first] = datas[i].first;
			lastsi[datas[i].second.first] = i;
		}
	}
	for (i=0; i<n; ++i) {
		datas[i].second.first = sum[i] - partial_sum[i];
		datas[i].first = datas[i].second.second;
	}
	stable_sort(datas, datas + n);
	for (i=0; i<n; ++i) {
		printf("%d\n", datas[i].second.first);
	}
	return 0;
}

Compilation message

ball.cpp: In function 'int main()':
ball.cpp:12:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
ball.cpp:14:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &datas[i].second.first, &datas[i].first);
                                                         ^

Subtask #1

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	132 ms	12 KB	Output is correct
2	Correct	138 ms	14 KB	Output is correct
3	Correct	131 ms	17 KB	Output is correct
4	Correct	137 ms	19 KB	Output is correct
5	Correct	136 ms	21 KB	Output is correct
6	Correct	6 ms	21 KB	Output is correct
7	Correct	6 ms	21 KB	Output is correct
8	Correct	6 ms	21 KB	Output is correct
9	Correct	6 ms	21 KB	Output is correct
10	Correct	6 ms	21 KB	Output is correct
11	Correct	121 ms	22 KB	Output is correct
12	Correct	119 ms	23 KB	Output is correct
13	Correct	121 ms	25 KB	Output is correct
14	Correct	120 ms	26 KB	Output is correct
15	Correct	118 ms	28 KB	Output is correct
16	Correct	131 ms	31 KB	Output is correct
17	Correct	118 ms	33 KB	Output is correct
18	Correct	131 ms	35 KB	Output is correct
19	Correct	128 ms	38 KB	Output is correct
20	Correct	140 ms	40 KB	Output is correct