Submission #70545341

Source Code Expand

Copy
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
int cmp(const void* x, const void* y) {
  int64_t a = *(const int64_t*)x, b = *(const int64_t*)y;
  return (a > b) - (a < b);
}
int N;
int64_t M;
int C;
int64_t A[512345];
int hito_cnt;
struct hito_s {
  int64_t pos;
  int cnt;
} hito[512345 * 2];
int hito_sum[512345 * 2];
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

int cmp(const void* x, const void* y) {
	int64_t a = *(const int64_t*)x, b = *(const int64_t*)y;
	return (a > b) - (a < b);
}

int N;
int64_t M;
int C;
int64_t A[512345];

int hito_cnt;
struct hito_s {
	int64_t pos;
	int cnt;
} hito[512345 * 2];
int hito_sum[512345 * 2];

int main(void) {
	int i;
	int64_t ans = 0;
	if (scanf("%d%" SCNd64 "%d", &N, &M, &C) != 3) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%" SCNd64, &A[i]) != 1) return 1;
	}
	qsort(A, N, sizeof(*A), cmp);
	hito_cnt = 1;
	hito[0].pos = 0;
	hito[0].cnt = 0;
	for (i = 0; i < N; i++) {
		if (hito[hito_cnt - 1].pos != A[i]) {
			hito_cnt++;
			hito[hito_cnt - 1].pos = A[i];
			hito[hito_cnt - 1].cnt = 0;
		}
		hito[hito_cnt - 1].cnt++;
	}
	for (i = 0; i < hito_cnt; i++) {
		hito[hito_cnt + i].pos = M + hito[i].pos;
		hito[hito_cnt + i].cnt = hito[i].cnt;
	}
	hito_sum[0] = hito[0].cnt;
	for (i = 1; i < hito_cnt * 2; i++) {
		hito_sum[i] = hito_sum[i - 1] + hito[i].cnt;
	}
	for (i = 0; i < hito_cnt; i++) {
		int l = i, ge = hito_cnt * 2 - 1;
		while (l + 1 < ge) {
			int m = l + (ge - l) / 2;
			if (hito_sum[m] - hito_sum[i] >= C) ge = m; else l = m;
		}
		ans += (hito[i + 1].pos - hito[i].pos) * (hito_sum[ge] - hito_sum[i]);
	}
	printf("%" PRId64 "\n", ans);
	return 0;
}

Submission Info

Submission Time
Task D - On AtCoder Conference
User mikecat
Language C (gcc 12.2.0)
Score 425
Code Size 1378 Byte
Status AC
Exec Time 153 ms
Memory 25120 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 425 / 425
Status
AC × 2
AC × 32
Set Name Test Cases
Sample example_00.txt, example_01.txt
All example_00.txt, example_01.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt
Case Name Status Exec Time Memory
example_00.txt AC 1 ms 1580 KiB
example_01.txt AC 1 ms 1684 KiB
hand_00.txt AC 57 ms 7244 KiB
hand_01.txt AC 57 ms 7320 KiB
hand_02.txt AC 149 ms 25120 KiB
hand_03.txt AC 41 ms 7336 KiB
hand_04.txt AC 1 ms 1620 KiB
hand_05.txt AC 1 ms 1568 KiB
random_00.txt AC 77 ms 9136 KiB
random_01.txt AC 76 ms 9092 KiB
random_02.txt AC 79 ms 9096 KiB
random_03.txt AC 99 ms 9096 KiB
random_04.txt AC 101 ms 9104 KiB
random_05.txt AC 101 ms 9104 KiB
random_06.txt AC 120 ms 16692 KiB
random_07.txt AC 119 ms 16380 KiB
random_08.txt AC 122 ms 15680 KiB
random_09.txt AC 78 ms 9128 KiB
random_10.txt AC 66 ms 8044 KiB
random_11.txt AC 71 ms 9060 KiB
random_12.txt AC 74 ms 9104 KiB
random_13.txt AC 99 ms 9164 KiB
random_14.txt AC 98 ms 9100 KiB
random_15.txt AC 78 ms 9064 KiB
random_16.txt AC 113 ms 9092 KiB
random_17.txt AC 115 ms 9104 KiB
random_18.txt AC 81 ms 9168 KiB
random_19.txt AC 125 ms 9164 KiB
random_20.txt AC 123 ms 9172 KiB
random_21.txt AC 123 ms 16564 KiB
random_22.txt AC 142 ms 15432 KiB
random_23.txt AC 153 ms 23460 KiB
Facebook Twitter Telegram Share

2025-10-30 (Thu)
07:46:46 +09:00

More…