oj.uz

답안 #20204

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
20204 2016-03-27T13:38:46 Z kipa00 컬러볼 (KOI15_ball) C++
25 / 25
 140 ms 40 KB 
#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

# 결과 실행 시간 메모리 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