#365428 (C) No.738 平らな農地

• 問題: No.738 平らな農地
• ユーザー: bal4u
• 提出日時: 2019-08-05 07:46:58
• 言語: C (gcc 12.3.0)
• 結果: AC
• 実行時間: 23 ms / 2,000 ms
• コード長: 4,436 bytes
• コンパイル時間: 1,117 ms
• コンパイル使用メモリ: 31,800 KB
• 実行使用メモリ: 4,384 KB
• 最終ジャッジ日時: 2023-09-25 13:34:25
• 合計ジャッジ時間: 6,282 ms
• ジャッジサーバーID （参考情報）: judge13 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,376 KB
testcase_01	AC	1 ms; 4,376 KB
testcase_02	AC	0 ms; 4,380 KB
testcase_03	AC	1 ms; 4,376 KB
testcase_04	AC	0 ms; 4,376 KB
testcase_05	AC	1 ms; 4,380 KB
testcase_06	AC	1 ms; 4,380 KB
testcase_07	AC	1 ms; 4,380 KB
testcase_08	AC	1 ms; 4,376 KB
testcase_09	AC	1 ms; 4,380 KB
testcase_10	AC	1 ms; 4,380 KB
testcase_11	AC	1 ms; 4,376 KB
testcase_12	AC	1 ms; 4,380 KB
testcase_13	AC	1 ms; 4,376 KB
testcase_14	AC	1 ms; 4,376 KB
testcase_15	AC	16 ms; 4,376 KB
testcase_16	AC	15 ms; 4,376 KB
testcase_17	AC	14 ms; 4,376 KB
testcase_18	AC	14 ms; 4,376 KB
testcase_19	AC	16 ms; 4,376 KB
testcase_20	AC	15 ms; 4,376 KB
testcase_21	AC	15 ms; 4,376 KB
testcase_22	AC	15 ms; 4,376 KB
testcase_23	AC	15 ms; 4,376 KB
testcase_24	AC	14 ms; 4,376 KB
testcase_25	AC	1 ms; 4,376 KB
testcase_26	AC	0 ms; 4,376 KB
testcase_27	AC	1 ms; 4,376 KB
testcase_28	AC	1 ms; 4,376 KB
testcase_29	AC	1 ms; 4,376 KB
testcase_30	AC	0 ms; 4,376 KB
testcase_31	AC	1 ms; 4,376 KB
testcase_32	AC	1 ms; 4,384 KB
testcase_33	AC	1 ms; 4,376 KB
testcase_34	AC	1 ms; 4,380 KB
testcase_35	AC	1 ms; 4,384 KB
testcase_36	AC	1 ms; 4,376 KB
testcase_37	AC	1 ms; 4,380 KB
testcase_38	AC	1 ms; 4,380 KB
testcase_39	AC	1 ms; 4,380 KB
testcase_40	AC	1 ms; 4,380 KB
testcase_41	AC	1 ms; 4,380 KB
testcase_42	AC	1 ms; 4,380 KB
testcase_43	AC	1 ms; 4,376 KB
testcase_44	AC	1 ms; 4,380 KB
testcase_45	AC	18 ms; 4,380 KB
testcase_46	AC	16 ms; 4,380 KB
testcase_47	AC	17 ms; 4,380 KB
testcase_48	AC	17 ms; 4,376 KB
testcase_49	AC	17 ms; 4,376 KB
testcase_50	AC	18 ms; 4,376 KB
testcase_51	AC	17 ms; 4,380 KB
testcase_52	AC	16 ms; 4,380 KB
testcase_53	AC	16 ms; 4,376 KB
testcase_54	AC	17 ms; 4,376 KB
testcase_55	AC	17 ms; 4,376 KB
testcase_56	AC	16 ms; 4,376 KB
testcase_57	AC	16 ms; 4,380 KB
testcase_58	AC	17 ms; 4,380 KB
testcase_59	AC	18 ms; 4,376 KB
testcase_60	AC	18 ms; 4,376 KB
testcase_61	AC	18 ms; 4,376 KB
testcase_62	AC	16 ms; 4,376 KB
testcase_63	AC	17 ms; 4,380 KB
testcase_64	AC	16 ms; 4,376 KB
testcase_65	AC	0 ms; 4,380 KB
testcase_66	AC	1 ms; 4,376 KB
testcase_67	AC	13 ms; 4,376 KB
testcase_68	AC	14 ms; 4,376 KB
testcase_69	AC	14 ms; 4,380 KB
testcase_70	AC	14 ms; 4,380 KB
testcase_71	AC	2 ms; 4,380 KB
testcase_72	AC	5 ms; 4,376 KB
testcase_73	AC	6 ms; 4,380 KB
testcase_74	AC	5 ms; 4,376 KB
testcase_75	AC	18 ms; 4,376 KB
testcase_76	AC	14 ms; 4,380 KB
testcase_77	AC	20 ms; 4,376 KB
testcase_78	AC	23 ms; 4,380 KB
testcase_79	AC	18 ms; 4,376 KB
testcase_80	AC	16 ms; 4,380 KB
testcase_81	AC	15 ms; 4,376 KB
testcase_82	AC	13 ms; 4,380 KB
testcase_83	AC	4 ms; 4,376 KB
testcase_84	AC	16 ms; 4,376 KB
testcase_85	AC	4 ms; 4,376 KB
testcase_86	AC	14 ms; 4,376 KB
testcase_87	AC	21 ms; 4,384 KB
testcase_88	AC	21 ms; 4,380 KB
testcase_89	AC	1 ms; 4,380 KB
testcase_90	AC	0 ms; 4,380 KB
testcase_91	AC	1 ms; 4,380 KB

コンパイルメッセージ

main.c: 関数 ‘in’ 内:
main.c:11:14: 警告: 関数 ‘getchar_unlocked’ の暗黙的な宣言です [-Wimplicit-function-declaration]
   11 | #define gc() getchar_unlocked()
      |              ^~~~~~~~~~~~~~~~
main.c:17:24: 備考: in expansion of macro ‘gc’
   17 |         int n = 0, c = gc();
      |                        ^~

ソースコード

// yukicoder: No.738 平らな農地
// 2019.8.4 bal4u

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

typedef long long ll;

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif

int in() {   // 非負整数の入力
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

#define MAX 100005
typedef struct { int v, id; } QUE;
QUE qmin[MAX]; int szqmin;
QUE qmax[MAX]; int szqmax;

#define PARENT(i) ((i)>>1)
#define LEFT(i)   ((i)<<1)
#define RIGHT(i)  (((i)<<1)+1)

void min_heapify(int i) {
	int l, r, min;
	l = LEFT(i), r = RIGHT(i);
	if (l < szqmin && (qmin[l].v < qmin[i].v ||
		(qmin[l].v == qmin[i].v && qmin[l].id < qmin[i].id))) min = l; else min = i;
	if (r < szqmin && (qmin[r].v < qmin[min].v ||
		(qmin[r].v == qmin[min].v && qmin[r].id < qmin[min].id))) min = r;
	if (min != i) {
		QUE qt = qmin[i]; qmin[i] = qmin[min]; qmin[min] = qt;
		min_heapify(min);
	}
}

int deqmin() {
	qmin[0] = qmin[--szqmin];
	min_heapify(0);
	return 1;
}

void enqmin(int id, int v) {
	int i, min;
	i = szqmin++;
	qmin[i].id = id, qmin[i].v = v;
	while (i > 0 && (qmin[min = PARENT(i)].v > qmin[i].v ||
		(qmin[min].v == qmin[i].v && qmin[min].id > qmin[i].id))) {
		QUE qt = qmin[i]; qmin[i] = qmin[min]; qmin[min] = qt;
		i = min;
	}
}

void max_heapify(int i) {
	int l, r, max;
	l = LEFT(i), r = RIGHT(i);
	if (l < szqmax && (qmax[l].v > qmax[i].v ||
		(qmax[l].v == qmax[i].v && qmax[l].id < qmax[i].id))) max = l; else max = i;
	if (r < szqmax && (qmax[r].v > qmax[max].v ||
		(qmax[r].v == qmax[max].v && qmax[r].id < qmax[max].id))) max = r;
	if (max != i) {
		QUE qt = qmax[i]; qmax[i] = qmax[max], qmax[max] = qt;
		max_heapify(max);
	}
}

void deqmax() {
	qmax[0] = qmax[--szqmax];
	max_heapify(0);
}

void enqmax(int id, int v) {
	int i, max;
	i = szqmax++;
	qmax[i].id = id, qmax[i].v = v;
	while (i > 0 && (qmax[max = PARENT(i)].v < qmax[i].v ||
		(qmax[max].v == qmax[i].v && qmax[max].id > qmax[i].id))) {
		QUE qt = qmax[i]; qmax[i] = qmax[max], qmax[max] = qt;
		i = max;
	}
}

#define ABS(x)    ((x)>=0?(x):-(x))
int N;
int a[MAX]; QUE b[MAX];

int cmp(const void *a, const void *b) {
	int t = ((QUE *)a)->v - ((QUE *)b)->v;
	if (t) return t;
	return ((QUE *)a)->id - ((QUE *)b)->id;
}

int main()
{
	int i, K, k, m, pm, ngmin, ngmax, diff;
	ll smin, smax, ans, t;

	N = in(), K = in(), k = K >> 1;
	if (K == 1) { puts("0"); return 0; }
#if 1
	if (K == 2) {
		m = in(), ans = 0x7fffffff;
		while (--N) {
			pm = m, m = in();
			if ((t = ABS(pm-m)) < ans) ans = t;
		}
		goto done;
	}
#endif
	for (i = 0; i < N; i++) a[i] = in();
	for (i = 0; i < K; i++) b[i].v = a[i], b[i].id = i;
	qsort(b, K, sizeof(QUE), cmp);
	m = b[k].v, smin = smax = 0, ngmin = ngmax = 0;
	for (i = 0; i < k; i++) enqmax(b[i].id, b[i].v), smax += m-b[i].v;
	for (     ; i < K; i++) enqmin(b[i].id, b[i].v), smin += b[i].v-m;
	ans = smin + smax; if (ans == 0) goto done;
	
//	printf("K=%d, k=%d, m=%d, szqmin=%d, szqmax=%d, smin=%lld, smax=%lld, ans=%lld\n", 
//		K, k, m, szqmin, szqmax, smin, smax, ans);
		
	for (i = K; i < N; i++) {
		int x = a[i-K];
		if (x > qmin[0].v) ngmin++, smin -= x-m;
		else if (x < qmax[0].v) ngmax++, smax -= m-x;
		else if (i-K == qmin[0].id) deqmin(), smin -= x-m;
		else if (i-K == qmax[0].id) deqmax(), smax -= m-x;
		else { printf("Panic median=%d, a[%]=%d\n", m, i-K, a[i-K]); return 0; }

//printf("szqmin=%d, ngmin=%d, smin=%lld, sqzmax=%d, ngmax=%d, smax=%lld\n",
//	szqmin, ngmin, smin, szqmax, ngmax, smax);

		if (a[i] >= m) enqmin(i, a[i]), smin += a[i]-m;
		else           enqmax(i, a[i]), smax += m-a[i];
		
		while (1) {
			QUE qt;
			diff = (szqmin-ngmin) - (szqmax-ngmax);
//printf("a[%d]=%d, diff=%d\n", i, a[i], diff);
			if (K & 1) {
				if (diff == 1) break;
			} else if (diff == 0) break;
			if (diff > 0) {
				qt = qmin[0], deqmin();
				if (qt.id <= i-K) ngmin--;
				else enqmax(qt.id, qt.v), smin -= qt.v-m, smax += m-qt.v;
			} else {
				qt = qmax[0], deqmax();
				if (qt.id <= i-K) ngmax--;
				else enqmin(qt.id, qt.v), smin += qt.v-m, smax -= m-qt.v;
			}
		}
		pm = m;
		if (diff >= 0) m = qmin[0].v; else m = qmax[0].v;
		if (m != pm) smin += (ll)(pm-m)*(szqmin-ngmin), smax += (ll)(m-pm)*(szqmax-ngmax);
		t = smin + smax; if (t < ans) { ans = t; if (ans == 0) goto done; }
//printf("pm=%d, m=%d, smin=%lld, smax=%lld, t=%lld, ans=%lld\n\n", pm,m,smin,smax,t,ans);
	}
done:
	printf("%lld\n", ans);
	return 0;
}