(cache)Submission #77235996 - Tokio Marine & Nichido Fire Insurance Programming Contest 2026 (AtCoder Beginner Contest 459)

Contest Duration: 2026-05-23(Sat) 21:00 - 2026-05-23(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #77235996

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
/* 座標変換を挟むことで、通常「指定の値以下」の和を求めるBITで「指定の値以上」の和を求める */
#define BIT_MAX 312345
int bit_table[BIT_MAX];
void bit_add(int pos, int value) {
  pos = BIT_MAX - pos - 1;
  while (pos <= BIT_MAX) {
    bit_table[pos - 1] += value;
    pos += pos & (-pos);
  }
}
int bit_sum(int pos) {
  int sum = 0;
  pos = BIT_MAX - pos - 1;
  while (pos > 0) {
    sum += bit_table[pos - 1];
    pos -= pos & (-pos);
  }
  return sum;
}
int N, Q;
int query[312345][2];
int count[312345];
int main(void) {
  int i;
  int offset = 0;
  if (scanf("%d%d", &N, &Q) != 2) return 1;
  for (i = 0; i < Q; i++) {
    if (scanf("%d%d", &query[i][0], &query[i][1]) != 2) return 1;
  }
  bit_add(0, N);
  for (i = 0; i < Q; i++) {
    if (query[i][0] == 1) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

/* 座標変換を挟むことで、通常「指定の値以下」の和を求めるBITで「指定の値以上」の和を求める */

#define BIT_MAX 312345

int bit_table[BIT_MAX];

void bit_add(int pos, int value) {
	pos = BIT_MAX - pos - 1;
	while (pos <= BIT_MAX) {
		bit_table[pos - 1] += value;
		pos += pos & (-pos);
	}
}

int bit_sum(int pos) {
	int sum = 0;
	pos = BIT_MAX - pos - 1;
	while (pos > 0) {
		sum += bit_table[pos - 1];
		pos -= pos & (-pos);
	}
	return sum;
}

int N, Q;
int query[312345][2];

int count[312345];

int main(void) {
	int i;
	int offset = 0;
	if (scanf("%d%d", &N, &Q) != 2) return 1;
	for (i = 0; i < Q; i++) {
		if (scanf("%d%d", &query[i][0], &query[i][1]) != 2) return 1;
	}
	bit_add(0, N);
	for (i = 0; i < Q; i++) {
		if (query[i][0] == 1) {
			bit_add(count[query[i][1]], -1);
			count[query[i][1]]++;
			bit_add(count[query[i][1]], 1);
			if (bit_sum(offset + 1) == N) offset++;
		} else if (query[i][0] == 2) {
			printf("%d\n", bit_sum(query[i][1] + offset));
		}
	}
	return 0;
}

Submission Info

Submission Time	2026-07-06 08:00:23
Task	C - Drop Blocks
User	mikecat
Language	C23 (GCC 14.2.0)
Score	300
Code Size	1100 Byte
Status	AC
Exec Time	42 ms
Memory	5344 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

300 / 300

Status

× 1

× 50

Set Name	Test Cases
Sample	example_00.txt
All	example_00.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, hand_09.txt, hand_10.txt, hand_11.txt, hand_12.txt, hand_13.txt, hand_14.txt, hand_15.txt, hand_16.txt, hand_17.txt, hand_18.txt, hand_19.txt, hand_20.txt, hand_21.txt, hand_22.txt, hand_23.txt, hand_24.txt, hand_25.txt, hand_26.txt, hand_27.txt, hand_28.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

Case Name	Status	Exec Time	Memory
example_00.txt	AC	1 ms	1616 KiB
hand_00.txt	AC	29 ms	5048 KiB
hand_01.txt	AC	29 ms	5144 KiB
hand_02.txt	AC	42 ms	4052 KiB
hand_03.txt	AC	35 ms	4124 KiB
hand_04.txt	AC	33 ms	4584 KiB
hand_05.txt	AC	35 ms	4064 KiB
hand_06.txt	AC	31 ms	3896 KiB
hand_07.txt	AC	28 ms	5204 KiB
hand_08.txt	AC	34 ms	3992 KiB
hand_09.txt	AC	31 ms	4524 KiB
hand_10.txt	AC	30 ms	4304 KiB
hand_11.txt	AC	30 ms	5164 KiB
hand_12.txt	AC	31 ms	5144 KiB
hand_13.txt	AC	38 ms	4052 KiB
hand_14.txt	AC	39 ms	4564 KiB
hand_15.txt	AC	38 ms	4304 KiB
hand_16.txt	AC	1 ms	1616 KiB
hand_17.txt	AC	39 ms	3996 KiB
hand_18.txt	AC	28 ms	5288 KiB
hand_19.txt	AC	28 ms	5220 KiB
hand_20.txt	AC	28 ms	5344 KiB
hand_21.txt	AC	34 ms	5248 KiB
hand_22.txt	AC	32 ms	5288 KiB
hand_23.txt	AC	36 ms	4960 KiB
hand_24.txt	AC	34 ms	5144 KiB
hand_25.txt	AC	1 ms	1488 KiB
hand_26.txt	AC	0 ms	1472 KiB
hand_27.txt	AC	4 ms	3044 KiB
hand_28.txt	AC	32 ms	4280 KiB
random_00.txt	AC	38 ms	4688 KiB
random_01.txt	AC	35 ms	4068 KiB
random_02.txt	AC	38 ms	4048 KiB
random_03.txt	AC	39 ms	4052 KiB
random_04.txt	AC	41 ms	4160 KiB
random_05.txt	AC	34 ms	4328 KiB
random_06.txt	AC	35 ms	4072 KiB
random_07.txt	AC	41 ms	3896 KiB
random_08.txt	AC	35 ms	4072 KiB
random_09.txt	AC	36 ms	4196 KiB
random_10.txt	AC	39 ms	3992 KiB
random_11.txt	AC	35 ms	4048 KiB
random_12.txt	AC	41 ms	4064 KiB
random_13.txt	AC	39 ms	4072 KiB
random_14.txt	AC	37 ms	4072 KiB
random_15.txt	AC	31 ms	4800 KiB
random_16.txt	AC	38 ms	4012 KiB
random_17.txt	AC	33 ms	4816 KiB
random_18.txt	AC	40 ms	3896 KiB
random_19.txt	AC	36 ms	4224 KiB