(cache)Submission #75322400 - Denso Create Programming Contest 2026（AtCoder Beginner Contest 443）

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

Submission #75322400

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>
#include <string.h>
#include <inttypes.h>
/* 範囲add、範囲min */
#define KI_MAX_MAX (1 << 19) /* 524288 */
#define INF 1010101010
int onh(int a, int b) { /* ookiku nai hou */
  return a <= b ? a : b;
}
int ki_max;
int ki[KI_MAX_MAX * 2 - 1], ki_all[KI_MAX_MAX * 2 - 1];
void ki_init(int max) {
  for (ki_max = 1; ki_max < max; ki_max <<= 1);
  memset(ki, 0, sizeof(*ki) * (ki_max * 2 - 1));
  memset(ki_all, 0, sizeof(*ki_all) * (ki_max * 2 - 1));
}
int ki_add_i(int idx, int ss, int se, int qs, int qe, int delta) {
  if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
    ki_all[idx] += delta;
  } else if (se <= qs || qe <= ss) { /* 完全に外れている */
    /* 何もしない */
  } else {
    int sm = ss + (se - ss) / 2;
    ki[idx] = onh(
      ki_add_i(idx * 2 + 1, ss, sm, qs, qe, delta),
      ki_add_i(idx * 2 + 2, sm, se, qs, qe, delta)
    );
  }
  return ki[idx] + ki_all[idx];
}
void ki_add(int qs, int qe, int delta) {
  ki_add_i(0, 0, ki_max, qs, qe, delta);
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <string.h>
#include <inttypes.h>

/* 範囲add、範囲min */

#define KI_MAX_MAX (1 << 19) /* 524288 */
#define INF 1010101010

int onh(int a, int b) { /* ookiku nai hou */
	return a <= b ? a : b;
}

int ki_max;
int ki[KI_MAX_MAX * 2 - 1], ki_all[KI_MAX_MAX * 2 - 1];

void ki_init(int max) {
	for (ki_max = 1; ki_max < max; ki_max <<= 1);
	memset(ki, 0, sizeof(*ki) * (ki_max * 2 - 1));
	memset(ki_all, 0, sizeof(*ki_all) * (ki_max * 2 - 1));
}

int ki_add_i(int idx, int ss, int se, int qs, int qe, int delta) {
	if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		ki_all[idx] += delta;
	} else if (se <= qs || qe <= ss) { /* 完全に外れている */
		/* 何もしない */
	} else {
		int sm = ss + (se - ss) / 2;
		ki[idx] = onh(
			ki_add_i(idx * 2 + 1, ss, sm, qs, qe, delta),
			ki_add_i(idx * 2 + 2, sm, se, qs, qe, delta)
		);
	}
	return ki[idx] + ki_all[idx];
}

void ki_add(int qs, int qe, int delta) {
	ki_add_i(0, 0, ki_max, qs, qe, delta);
}

int ki_get_i(int idx, int ss, int se, int qs, int qe) {
	if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		return ki[idx] + ki_all[idx];
	} else if (se <= qs || qe <= ss) { /* 完全に外れている */
		return INF;
	} else {
		int sm = ss + (se - ss) / 2;
		return onh(
			ki_get_i(idx * 2 + 1, ss, sm, qs, qe),
			ki_get_i(idx * 2 + 2, sm, se, qs, qe)
		) + ki_all[idx];
	}
}

int ki_get(int qs, int qe) {
	return ki_get_i(0, 0, ki_max, qs, qe);
}

int N;
int R[312345];

int main(void) {
	int T, tc;
	if (scanf("%d", &T) != 1) return 1;
	for (tc = 0; tc < T; tc++) {
		int i;
		int64_t ans = 0;
		if (scanf("%d", &N) != 1) return 1;
		for (i = 0; i < N; i++) {
			if (scanf("%d", &R[i]) != 1) return 1;
		}
		ki_init(N);
		for (i = 0; i < N; i++) {
			ki_add(i, i + 1, R[i] + i);
		}
		ans += R[0] - ki_get(0, N);
		for (i = 1; i < N; i++) {
			ki_add(0, i, 1);
			ki_add(i, N, -1);
			ans += R[i] - ki_get(0, N);
		}
		printf("%" PRId64 "\n", ans);
	}
	return 0;
}

/*

一番 R_i が小さいところは、動かさない (動かしても有利にならない)
その次は……？
それぞれの初期位置から、両側に斜めに基準線を出し、それらの min のところに配置する
順に見ていき、横に1個ずれるとずれた先より左は +1、ずれた先とそれより右は -1

*/

Submission Info

Submission Time	2026-04-28 07:55:59
Task	D - Pawn Line
User	mikecat
Language	C23 (GCC 14.2.0)
Score	400
Code Size	2484 Byte
Status	AC
Exec Time	155 ms
Memory	11224 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

400 / 400

Status

× 1

× 72

Set Name	Test Cases
Sample	sample_01.txt
All	killer_01.txt, killer_02.txt, killer_03.txt, killer_04.txt, killer_05.txt, killer_06.txt, sample_01.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45.txt, test_46.txt, test_47.txt, test_48.txt, test_49.txt, test_50.txt, test_51.txt, test_52.txt, test_53.txt, test_54.txt, test_55.txt, test_56.txt, test_57.txt, test_58.txt, test_59.txt, test_60.txt, test_61.txt, test_62.txt, test_63.txt, test_64.txt, test_65.txt

Case Name	Status	Exec Time	Memory
killer_01.txt	AC	137 ms	10976 KiB
killer_02.txt	AC	139 ms	10960 KiB
killer_03.txt	AC	139 ms	11052 KiB
killer_04.txt	AC	138 ms	11040 KiB
killer_05.txt	AC	155 ms	10976 KiB
killer_06.txt	AC	144 ms	10952 KiB
sample_01.txt	AC	0 ms	1752 KiB
test_01.txt	AC	9 ms	1580 KiB
test_02.txt	AC	15 ms	1584 KiB
test_03.txt	AC	17 ms	1608 KiB
test_04.txt	AC	27 ms	1584 KiB
test_05.txt	AC	30 ms	1604 KiB
test_06.txt	AC	31 ms	1644 KiB
test_07.txt	AC	25 ms	1696 KiB
test_08.txt	AC	38 ms	1584 KiB
test_09.txt	AC	34 ms	1612 KiB
test_10.txt	AC	38 ms	1608 KiB
test_11.txt	AC	39 ms	1584 KiB
test_12.txt	AC	70 ms	1628 KiB
test_13.txt	AC	71 ms	1616 KiB
test_14.txt	AC	95 ms	1760 KiB
test_15.txt	AC	97 ms	1716 KiB
test_16.txt	AC	117 ms	2272 KiB
test_17.txt	AC	118 ms	2220 KiB
test_18.txt	AC	117 ms	2272 KiB
test_19.txt	AC	116 ms	2252 KiB
test_20.txt	AC	141 ms	10924 KiB
test_21.txt	AC	139 ms	11224 KiB
test_22.txt	AC	139 ms	11028 KiB
test_23.txt	AC	139 ms	11096 KiB
test_24.txt	AC	147 ms	11104 KiB
test_25.txt	AC	139 ms	10956 KiB
test_26.txt	AC	141 ms	10972 KiB
test_27.txt	AC	138 ms	11056 KiB
test_28.txt	AC	139 ms	11040 KiB
test_29.txt	AC	142 ms	10956 KiB
test_30.txt	AC	133 ms	6368 KiB
test_31.txt	AC	132 ms	6216 KiB
test_32.txt	AC	144 ms	11028 KiB
test_33.txt	AC	132 ms	6368 KiB
test_34.txt	AC	138 ms	6688 KiB
test_35.txt	AC	136 ms	6736 KiB
test_36.txt	AC	127 ms	4244 KiB
test_37.txt	AC	136 ms	6528 KiB
test_38.txt	AC	143 ms	10952 KiB
test_39.txt	AC	133 ms	6496 KiB
test_40.txt	AC	138 ms	10988 KiB
test_41.txt	AC	138 ms	10932 KiB
test_42.txt	AC	139 ms	10976 KiB
test_43.txt	AC	137 ms	10972 KiB
test_44.txt	AC	138 ms	10952 KiB
test_45.txt	AC	138 ms	10928 KiB
test_46.txt	AC	140 ms	11008 KiB
test_47.txt	AC	140 ms	11040 KiB
test_48.txt	AC	139 ms	11080 KiB
test_49.txt	AC	138 ms	10812 KiB
test_50.txt	AC	138 ms	10924 KiB
test_51.txt	AC	140 ms	10976 KiB
test_52.txt	AC	140 ms	10972 KiB
test_53.txt	AC	139 ms	10976 KiB
test_54.txt	AC	141 ms	10928 KiB
test_55.txt	AC	140 ms	10956 KiB
test_56.txt	AC	140 ms	11028 KiB
test_57.txt	AC	139 ms	10976 KiB
test_58.txt	AC	138 ms	10956 KiB
test_59.txt	AC	140 ms	10952 KiB
test_60.txt	AC	135 ms	10952 KiB
test_61.txt	AC	137 ms	10956 KiB
test_62.txt	AC	138 ms	10976 KiB
test_63.txt	AC	144 ms	11156 KiB
test_64.txt	AC	136 ms	10928 KiB
test_65.txt	AC	137 ms	11104 KiB