結果

問題 No.1649 Manhattan Square
コンテスト
ユーザー 👑 ygussany
提出日時 2021-08-01 15:06:01
言語 C
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 3,509 bytes
コンパイル時間 527 ms
コンパイル使用メモリ 35,120 KB
実行使用メモリ 17,300 KB
最終ジャッジ日時 2024-10-03 16:09:40
合計ジャッジ時間 6,711 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 TLE * 1 -- * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

#define SIZE 10000
#define NUM 21
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