結果
問題 | No.1709 Indistinguishable by MEX |
ユーザー |
|
提出日時 | 2022-07-05 01:42:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 141 ms / 2,000 ms |
コード長 | 1,937 bytes |
コンパイル時間 | 1,551 ms |
コンパイル使用メモリ | 123,496 KB |
実行使用メモリ | 14,208 KB |
最終ジャッジ日時 | 2024-12-14 23:07:14 |
合計ジャッジ時間 | 4,746 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#pragma GCC optimize("Ofast")#include <iostream>#include <vector>#include <algorithm>#include <map>#include <queue>#include <cstdio>#include <ctime>#include <assert.h>#include <chrono>#include <random>#include <numeric>#include <set>#include <deque>#include <stack>#include <sstream>#include <utility>#include <cstring>#include <unordered_map>#include <unordered_set>#include <tuple>#include <array>#include <bitset>using namespace std;typedef long long int ll;typedef unsigned long long ull;mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());ll myRand(ll B) {return (ull)rng() % B;}inline double time() {return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;}constexpr ll mod = 998244353;int main() {cin.tie(nullptr);ios::sync_with_stdio(false);int q; q = 1;while(q--){int n; cin >> n;ll res = 1;vector<int> a(n);vector<int> p(n);for(int i=0;i<n;i++){cin >> a[i];p[a[i]] = i;}int l = p[0], r = p[0];set<int> st;st.insert(0);ll cur = 0;for(int i=1;i<n;i++){if(st.find(i) != st.end()){res *= cur;res %= mod;cur--;}else{int id = p[i];if(id < l){for(int j=id;j<l;j++){cur++;st.insert(a[j]);}l = id;}else{for(int j=r+1;j<=id;j++){cur++;st.insert(a[j]);}r = id;}cur--;}}cout << res << "\n";}}