結果

問題 No.3371 Add Insert Operations
コンテスト
ユーザー tokitsukaze
提出日時 2026-02-04 11:16:23
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 619 ms / 2,000 ms
コード長 1,762 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,161 ms
コンパイル使用メモリ 235,284 KB
実行使用メモリ 76,004 KB
最終ジャッジ日時 2026-02-04 11:16:36
合計ジャッジ時間 12,750 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5, mod = 998244353;
int n, OP, a[MAXN], id[MAXN], pre[MAXN], suf[MAXN], fac[MAXN], siz[MAXN], in[MAXN];
map<pair<int, int>, int> mp;
vector<int> e[MAXN];

int qpow(int a, int b){ int res = 1; for(; b; b >>= 1, a = 1ll * a * a % mod) if(b & 1) res = 1ll * res * a % mod; return res; }

void dfs(int u){
	siz[u] = 1;
	for(int v : e[u]) dfs(v), siz[u] += siz[v];
}

void solve(){
	cin >> n; for(int i = 1; i <= n; ++i) cin >> a[i], id[i] = i, suf[i] = i + 1, pre[i] = i - 1;
	sort(id + 1, id + n + 1, [](int p, int q){ return a[p] < a[q]; });
	mp.clear(); set<pair<int, int>> st, st1;
	for(int i = 1; i <= n; ++i) st1.insert({a[i], i});
	for(int i = 1; i <= n; ++i){
		int u = st1.begin()->second, x = pre[u], y = suf[u]; st1.erase(st1.begin());
		if(a[u]) return cout << "0\n", void();
		if(x) st.insert({x, u}), st1.erase({a[x], x}), st1.insert({--a[x], x});
		if(y <= n) st.insert({y, u}), st1.erase({a[y], y}), st1.insert({--a[y], y});
		if(mp[{u, x}]) st.erase({x, mp[{u, x}]});
		if(mp[{u, y}]) st.erase({y, mp[{u, y}]});
		mp[{x, y}] = mp[{y, x}] = u;
		suf[pre[u]] = suf[u], pre[suf[u]] = pre[u];
	}
	for(int i = 1; i <= n; ++i) vector<int>().swap(e[i]), in[i] = 0;
	for(auto [x, y] : st) if(x && y) e[x].push_back(y), in[y]++;
	if(count(in + 1, in + n + 1, 0) != 1) return cout << "0\n", void();
	int rt = min_element(in + 1, in + n + 1) - in;
	dfs(rt);
	fac[0] = 1; for(int i = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
	int ans = fac[n]; for(int i = 1; i <= n; ++i) ans = 1ll * ans * qpow(siz[i], mod - 2) % mod;
	cout << (OP ? ans : 1) << '\n';
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int T; T=1,OP=1; while(T--) solve();
	
	return 0;
}
0