#685236 (C) No.1649 Manhattan Square

提出ソース

結果

問題	No.1649 Manhattan Square
ユーザー	ygussany
提出日時	2021-08-01 15:00:44
言語	C (gcc 12.3.0)
結果	WA
実行時間	-
コード長	3,508 bytes
コンパイル時間	504 ms
コンパイル使用メモリ	35,052 KB
実行使用メモリ	10,604 KB
最終ジャッジ日時	2024-10-03 16:11:36
合計ジャッジ時間	39,979 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 7,420 KB
testcase_01	AC	3 ms 8,444 KB
testcase_02	AC	11 ms 7,080 KB
testcase_03	AC	10 ms 7,592 KB
testcase_04	AC	10 ms 8,480 KB
testcase_05	AC	11 ms 7,596 KB
testcase_06	AC	11 ms 7,068 KB
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	WA	-
testcase_41	WA	-
testcase_42	AC	93 ms 10,448 KB
testcase_43	AC	2 ms 7,680 KB
testcase_44	AC	3 ms 8,572 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <stdio.h>

#define SIZE 450
#define NUM 450
const int Mod = 998244353;

typedef struct List {
	struct List *next;
	int v;
} list;

typedef struct {
	int key, id;
} data;

void merge_sort(data x[], int n)
{
	static data y[200001] = {};
	if (n <= 1) return;
	merge_sort(&(x[0]), n/2);
	merge_sort(&(x[n/2]), (n+1)/2);
	
	int i, p, q;
	for (i = 0, p = 0, q = n/2; i < n; i++) {
		if (p >= n/2) y[i] = x[q++];
		else if (q >= n) y[i] = x[p++];
		else y[i] = (x[p].key < x[q].key)? x[p++]: x[q++];
	}
	for (i = 0; i < n; i++) x[i] = y[i];
}

int main()
{
	int i, N, x[200001], y[200001];
	data d[200001];
	scanf("%d", &N);
	for (i = 1; i <= N; i++) scanf("%d %d", &(x[i]), &(y[i]));

	int j, m, n, X[200001], Y[200001];
	long long ans[2] = {}, sum;
	for (i = 0; i < N; i++) {
		d[i].key = y[i+1];
		d[i].id = i + 1;
	}
	merge_sort(d, N);
	for (i = 0, sum = 0; i < N; i++) {
		j = d[i].id;
		ans[0] += (long long)y[j] * y[j] % Mod * (N - 1) % Mod;
		ans[0] += Mod - sum * y[j] * 2 % Mod;
		sum += y[j];
		while (sum >= Mod) sum -= Mod;
	}
	for (i = 1, n = 0, Y[0] = y[d[0].id], y[d[0].id] = 0; i < N; i = j) {
		for (j = i; j < N && y[d[j].id] == Y[n]; j++) y[d[j].id] = n;
		if (j < N) {
			Y[++n] = y[d[j].id];
			y[d[j++].id] = n;
		}
	}
	n++;
	
	for (i = 0; i < N; i++) {
		d[i].key = x[i+1];
		d[i].id = i + 1;
	}
	merge_sort(d, N);
	for (i = 0, sum = 0; i < N; i++) {
		j = d[i].id;
		ans[0] += (long long)x[j] * x[j] % Mod * (N - 1) % Mod;
		ans[0] += Mod - sum * x[j] * 2 % Mod;
		sum += x[j];
		while (sum >= Mod) sum -= Mod;
	}
	for (i = 1, m = 0, X[0] = x[d[0].id], x[d[0].id] = 0; i < N; i = j) {
		for (j = i; j < N && x[d[j].id] == X[m]; j++) x[d[j].id] = m;
		if (j < N) {
			X[++m] = x[d[j].id];
			x[d[j++].id] = m;
		}
	}
	m++;
	
	int k, l, p_num[200001] = {}, block_num[NUM] = {}, block_add[NUM] = {};
	long long p_sum[200001] = {}, block_xsum[NUM] = {}, block_ysum[NUM] = {}, block_total[NUM] = {};
	k = y[d[0].id];
	l = k / SIZE;
	p_num[k]++;
	block_num[l]++;
	block_ysum[l] = Y[k];
	if (block_ysum[l] >= Mod) block_ysum[l] -= Mod;
	for (i = 1; i < m; i++) {
		if (x[d[i].id] > x[d[i-1].id]) {
			for (j = 0; j <= (n - 1) / SIZE; j++) {
				block_add[j] += X[x[d[i].id]] - X[x[d[i-1].id]];
				block_xsum[j] += (long long)(X[x[d[i].id]] - X[x[d[i-1].id]]) * block_num[j] % Mod;
				if (block_xsum[j] >= Mod) block_xsum[j] -= Mod;
				block_total[j] += (X[x[d[i].id]] - X[x[d[i-1].id]]) * block_ysum[j] % Mod;
				if (block_total[j] >= Mod) block_total[j] -= Mod;
			}
		}
		
		k = y[d[i].id];
		l = k / SIZE;
		if (block_add[l] != 0) {
			for (j = l * SIZE; j < n && j < (l + 1) * SIZE; j++) {
				p_sum[j] += (long long)p_num[j] * block_add[l] % Mod;
				if (p_sum[j] >= Mod) p_sum[j] -= Mod;
			}
			block_add[l] = 0;
		}
		p_num[k]++;
		block_num[l]++;
		block_ysum[l] += Y[k];
		while (block_ysum[l] >= Mod) block_ysum[l] -= Mod;
		for (j = l * SIZE; j < k; j++) {
			ans[1] += (Y[k] - Y[j]) * p_sum[j] % Mod;
			if (ans[1] >= Mod) ans[1] -= Mod;
		}
		for (j++; j < (l + 1) * SIZE && j < n; j++) {
			ans[1] += (Y[j] - Y[k]) * p_sum[j] % Mod;
			if (ans[1] >= Mod) ans[1] -= Mod;
		}
		for (j = 0; j < l; j++) {
			ans[1] += (Y[k] * block_xsum[j] - block_total[j] + Mod) % Mod;
			if (ans[1] >= Mod) ans[1] -= Mod;
		}
		for (j++; j <= (n - 1) / SIZE; j++) {
			ans[1] += block_total[j] - Y[k] * block_xsum[j] % Mod;
			if (ans[1] >= Mod) ans[1] -= Mod;
			else if (ans[1] < 0) ans[1] += Mod;
		}
	}
	
	printf("%lld\n", (ans[0] + ans[1] * 2) % Mod);
	fflush(stdout);
	return 0;
}

yukicoder

結果

テストケース

ソースコード