結果

問題 No.1649 Manhattan Square
ユーザー ygussanyygussany
提出日時 2021-08-01 15:06:22
言語 C
(gcc 12.3.0)
結果
TLE  
実行時間 -
コード長 3,508 bytes
コンパイル時間 676 ms
コンパイル使用メモリ 34,952 KB
実行使用メモリ 16,640 KB
最終ジャッジ日時 2024-10-03 16:09:52
合計ジャッジ時間 6,306 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
10,880 KB
testcase_01 AC 3 ms
5,504 KB
testcase_02 AC 19 ms
5,504 KB
testcase_03 AC 19 ms
5,504 KB
testcase_04 AC 18 ms
5,504 KB
testcase_05 AC 19 ms
5,504 KB
testcase_06 AC 19 ms
5,504 KB
testcase_07 TLE -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

#define SIZE 5
#define NUM 40001
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;
}
0