結果

問題 No.3371 Add Insert Operations
コンテスト
ユーザー Naru820
提出日時 2025-11-01 16:20:16
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 228 ms / 2,000 ms
コード長 2,649 bytes
コンパイル時間 5,523 ms
コンパイル使用メモリ 334,292 KB
実行使用メモリ 35,228 KB
最終ジャッジ日時 2025-11-17 20:41:50
合計ジャッジ時間 9,678 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all>
#define fast std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr)
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using mint = atcoder::modint998244353;
constexpr ll inf = 2e18;
constexpr ll mod = 998244353;

static void judge(bool c) {
    std::cout << (c ? "Yes" : "No") << '\n';
}
// https://nyaannyaan.github.io/library/tree/cartesian-tree.hpp.html
template <typename T>
pair<vector<vector<int>>, int> CartesianTree(vector<T> &a) {
  int N = (int)a.size();
  vector<vector<int>> g(N);
  vector<int> p(N, -1), st;
  st.reserve(N);
  for (int i = 0; i < N; i++) {
    int prv = -1;
    while (!st.empty() && a[i] < a[st.back()]) {
      prv = st.back();
      st.pop_back();
    }
    if (prv != -1) p[prv] = i;
    if (!st.empty()) p[i] = st.back();
    st.push_back(i);
  }
  int root = -1;
  for (int i = 0; i < N; i++) {
    if (p[i] != -1)
      g[p[i]].push_back(i);
    else
      root = i;
  }
  return make_pair(g, root);
}
ll n,a[200000];
int main(){
    cin >> n;
    vector<int> p(n);
    set<int> zero,still;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        if(!a[i]) zero.insert(i);
        still.insert(i);
    }
    // 操作列を1つ構成する
    for(int i = 0; i < n; i++){
        if(zero.empty()){
            cout << 0 << endl;
            return 0;
        }
        int v = *zero.begin();
        zero.erase(zero.begin());
        p[v] = n - i;
        a[v] = inf;
        still.erase(v);
        auto it1 = still.lower_bound(v),it2 = still.upper_bound(v);
        if(it1 != still.begin()){
            it1--;
            a[*it1]--;
            if(a[*it1] == 0){
                zero.insert(*it1);
            }
            if(a[*it1] < 0){
                cout << 0 << endl;
                return 0;
            }
        }
        if(it2 != still.end()){
            a[*it2]--;
            if(a[*it2] == 0){
                zero.insert(*it2);
            }
            if(a[*it2] < 0){
                cout << 0 << endl;
                return 0;
            }
        }
    }
    // カルテシアンツリーを作る
    auto [g, par]= CartesianTree(p);

    // すべての頂点について部分木のサイズを求める
    vector<int> sz(n, 1);
    auto dfs = [&](auto&& f, int v) -> void {
        for(auto nv : g[v]){
            f(f, nv);
            sz[v] += sz[nv];
        }
    };
    dfs(dfs, par);
    // 答えの計算
    mint ans = 1;
    for(int i = 0; i < n; i++){
        ans /= sz[i];
        ans *= (i + 1);
    }
    cout << ans.val() << endl;
}
0