結果
問題 | No.1709 Indistinguishable by MEX |
ユーザー |
|
提出日時 | 2021-10-15 22:59:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 24 ms / 2,000 ms |
コード長 | 7,623 bytes |
コンパイル時間 | 2,065 ms |
コンパイル使用メモリ | 184,116 KB |
実行使用メモリ | 7,808 KB |
最終ジャッジ日時 | 2024-09-17 18:03:36 |
合計ジャッジ時間 | 3,822 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#pragma GCC optimize ("Ofast")#include<bits/stdc++.h>using namespace std;#define MD (998244353U)void*wmem;char memarr[96000000];template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};(*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );(*arr)=(T*)(*mem);(*mem)=((*arr)+x);}template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){walloc1d(arr, x2-x1, mem);(*arr) -= x1;}template<class T1> void sortA_L(int N, T1 a[], void *mem = wmem){sort(a, a+N);}template<class T1, class T2> void sortA_L(int N, T1 a[], T2 b[], void *mem = wmem){int i;pair<T1, T2>*arr;walloc1d(&arr, N, &mem);for(i=(0);i<(N);i++){arr[i].first = a[i];arr[i].second = b[i];}sort(arr, arr+N);for(i=(0);i<(N);i++){a[i] = arr[i].first;b[i] = arr[i].second;}}struct Modint{unsigned val;Modint(){val=0;}Modint(int a){val = ord(a);}Modint(unsigned a){val = ord(a);}Modint(long long a){val = ord(a);}Modint(unsigned long long a){val = ord(a);}inline unsigned ord(unsigned a){return a%MD;}inline unsigned ord(int a){a %= (int)MD;if(a < 0){a += MD;}return a;}inline unsigned ord(unsigned long long a){return a%MD;}inline unsigned ord(long long a){a %= (int)MD;if(a < 0){a += MD;}return a;}inline unsigned get(){return val;}inline Modint &operator++(){val++;if(val >= MD){val -= MD;}return *this;}inline Modint &operator--(){if(val == 0){val = MD - 1;}else{--val;}return *this;}inline Modint operator++(int a){Modint res(*this);val++;if(val >= MD){val -= MD;}return res;}inline Modint operator--(int a){Modint res(*this);if(val == 0){val = MD - 1;}else{--val;}return res;}inline Modint &operator+=(Modint a){val += a.val;if(val >= MD){val -= MD;}return *this;}inline Modint &operator-=(Modint a){if(val < a.val){val = val + MD - a.val;}else{val -= a.val;}return *this;}inline Modint &operator*=(Modint a){val = ((unsigned long long)val*a.val)%MD;return *this;}inline Modint &operator/=(Modint a){return *this *= a.inverse();}inline Modint operator+(Modint a){return Modint(*this)+=a;}inline Modint operator-(Modint a){return Modint(*this)-=a;}inline Modint operator*(Modint a){return Modint(*this)*=a;}inline Modint operator/(Modint a){return Modint(*this)/=a;}inline Modint operator+(int a){return Modint(*this)+=Modint(a);}inline Modint operator-(int a){return Modint(*this)-=Modint(a);}inline Modint operator*(int a){return Modint(*this)*=Modint(a);}inline Modint operator/(int a){return Modint(*this)/=Modint(a);}inline Modint operator+(long long a){return Modint(*this)+=Modint(a);}inline Modint operator-(long long a){return Modint(*this)-=Modint(a);}inline Modint operator*(long long a){return Modint(*this)*=Modint(a);}inline Modint operator/(long long a){return Modint(*this)/=Modint(a);}inline Modint operator-(void){Modint res;if(val){res.val=MD-val;}else{res.val=0;}return res;}inline operator bool(void){return val!=0;}inline operator int(void){return get();}inline operator long long(void){return get();}inline Modint inverse(){int a = val;int b = MD;int u = 1;int v = 0;int t;Modint res;while(b){t = a / b;a -= t * b;swap(a, b);u -= t * v;swap(u, v);}if(u < 0){u += MD;}res.val = u;return res;}inline Modint pw(unsigned long long b){Modint a(*this);Modint res;res.val = 1;while(b){if(b&1){res *= a;}b >>= 1;a *= a;}return res;}inline bool operator==(int a){return ord(a)==val;}inline bool operator!=(int a){return ord(a)!=val;}};inline Modint operator+(int a, Modint b){return Modint(a)+=b;}inline Modint operator-(int a, Modint b){return Modint(a)-=b;}inline Modint operator*(int a, Modint b){return Modint(a)*=b;}inline Modint operator/(int a, Modint b){return Modint(a)/=b;}inline Modint operator+(long long a, Modint b){return Modint(a)+=b;}inline Modint operator-(long long a, Modint b){return Modint(a)-=b;}inline Modint operator*(long long a, Modint b){return Modint(a)*=b;}inline Modint operator/(long long a, Modint b){return Modint(a)/=b;}inline int my_getchar(){static char buf[1048576];static int s = 1048576;static int e = 1048576;if(s == e && e == 1048576){e = fread(buf, 1, 1048576, stdin);s = 0;}if(s == e){return EOF;}return buf[s++];}inline void rd(int &x){int k;int m=0;x=0;for(;;){k = my_getchar();if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){k = my_getchar();if(k<'0'||k>'9'){break;}x=x*10+k-'0';}if(m){x=-x;}}struct MY_WRITER{char buf[1048576];int s;int e;MY_WRITER(){s = 0;e = 1048576;}~MY_WRITER(){if(s){fwrite(buf, 1, s, stdout);}}};MY_WRITER MY_WRITER_VAR;void my_putchar(int a){if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){fwrite(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);MY_WRITER_VAR.s = 0;}MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;}inline void wt_L(char a){my_putchar(a);}inline void wt_L(int x){int s=0;int m=0;char f[10];if(x<0){m=1;x=-x;}while(x){f[s++]=x%10;x/=10;}if(!s){f[s++]=0;}if(m){my_putchar('-');}while(s--){my_putchar(f[s]+'0');}}inline void wt_L(Modint x){int i;i = (int)x;wt_L(i);}template<class S, class T> inline S chmin(S &a, T b){if(a>b){a=b;}return a;}template<class S, class T> inline S chmax(S &a, T b){if(a<b){a=b;}return a;}int N;int P[200000+10];int id[200000+10];int main(){int i;wmem = memarr;rd(N);{int PiIOrLma;for(PiIOrLma=(0);PiIOrLma<(N);PiIOrLma++){rd(P[PiIOrLma]);}}for(i=(0);i<(N);i++){id[i] = i;}sortA_L(N, P, id);Modint ans;ans = 1;int l = 0;int r = 0;for(i=(0);i<(N);i++){if(i == 0){l = id[i];r = id[i];continue;}if(id[i] < l || id[i] > r){chmin(l, id[i]);chmax(r, id[i]);continue;}ans *= (r - l + 1 - i);}wt_L(ans);wt_L('\n');return 0;}// cLay version 20210405-1// --- original code ---// //no-unlocked// #define MD 998244353// int N;// int P[2d5+10];// int id[2d5+10];// {// rd(N, P(N));// rep(i, N) id[i] = i;// sortA(N, P, id);// Modint ans;// ans = 1;// int l = 0, r = 0;// rep(i, N){// if(i == 0){// l = id[i];// r = id[i];// continue;// }// if(id[i] < l || id[i] > r){// l <?= id[i];// r >?= id[i];// continue;// }// ans *= (r - l + 1 - i);// }// wt(ans);// }