結果

問題 No.3530 「」
コンテスト
ユーザー Carpenters-Cat
提出日時 2026-05-04 23:43:00
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 338 ms / 3,000 ms
コード長 1,818 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,122 ms
コンパイル使用メモリ 288,944 KB
実行使用メモリ 25,276 KB
最終ジャッジ日時 2026-05-04 23:43:15
合計ジャッジ時間 10,753 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using ll = long long;
vector<mint> p4, p3;
struct S {
	ll L;
	ll R;
	mint iv;
};
S op(S a, S b) {
	return S{a.L + b.L, a.R + b.R, 
	(p4[a.R] - p3[a.R]) * (p4[b.L] - p3[b.L]) * p4[a.L + b.R]
		+ a.iv * p3[b.L] * p4[b.R] + b.iv * p3[a.R] * p4[a.L]
	};
}
S e() {
	return S{0, 0, 0};
}
int main () {
	int N;
	cin >> N;
	p4.assign(N+1, 1);
	for (int i = 0; i < N; i ++) p4[i+1] = p4[i] * 4;
	p3.assign(N+1, 1);
	for (int i = 0; i < N; i ++) p3[i+1] = p3[i] * 3;
	std::vector<int> X(N), Y(N);
	for (int i = 0; i < N; i ++) cin >> X[i]>> Y[i];
	auto P = X;
	auto Q = Y;
	sort(P.begin(), P.end());
	P.erase(unique(P.begin(), P.end()), P.end());
	sort(Q.begin(), Q.end());
	Q.erase(unique(Q.begin(), Q.end()), Q.end());
	for (auto& a : X) {
		a = lower_bound(P.begin(), P.end(), a) - P.begin();
	}
	for (auto& a : Y) {
		a = lower_bound(Q.begin(), Q.end(), a) - Q.begin();
	}
	vector<vector<int>> Xs(N), Ys(N);
	for (int i = 0; i < N; i ++) {
		Xs[X[i]].push_back(Y[i]);
		Ys[Y[i]].push_back(X[i]);
	}
	mint ans = 0;
	segtree<S, op, e> sg(N);
	for (int i = 0; i < N; i ++) {
		auto s = sg.get(Y[i]);
		sg.set(Y[i], S{0, s.R+1, 0});
	}
	for (int i = 0; i + 1 < P.size(); i ++) {
		mint d = P[i+1] - P[i];
		for (auto& y : Xs[i]) {
			auto s = sg.get(y);
			sg.set(y, S{s.L+1, s.R-1, 0});
		}
		d *= sg.prod(0, N).iv;
		ans += d*2;
	}
	for (int i = 0; i < N; i ++) {
		sg.set(i, e());
	}
	for (int i = 0; i < N; i ++) {
		auto s = sg.get(X[i]);
		sg.set(X[i], S{0, s.R+1, 0});
	}
	for (int i = 0; i + 1 < Q.size(); i ++) {
		mint d = Q[i+1] - Q[i];
		for (auto& y : Ys[i]) {
			auto s = sg.get(y);
			sg.set(y, S{s.L+1, s.R-1, 0});
		}
		d *= sg.prod(0, N).iv;
		ans += d*2;
	}
	cout << ans.val() << endl;
}
0