結果
問題 | No.2250 Split Permutation |
ユーザー |
|
提出日時 | 2023-03-17 23:33:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 73 ms / 3,000 ms |
コード長 | 1,618 bytes |
コンパイル時間 | 605 ms |
コンパイル使用メモリ | 86,996 KB |
最終ジャッジ日時 | 2025-02-11 14:33:26 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:61:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 61 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:63:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 63 | for (i=0; i<n; i++) scanf("%d", &as[i]); | ~~~~~^~~~~~~~~~~~~~
ソースコード
#include<stdio.h>#include<string.h>#include<stdlib.h>#include <map>#include <vector>#include <queue>#include <deque>#include <set>#include <stack>#include <algorithm>#include <array>#include <unordered_set>#include <unordered_map>#include <string>using namespace std;bool rcmp(int a, int b) { return a>b; }typedef long long LL;#define MOD 998244353int cx[1<<19], mx;int ix[1<<19];int sumit(int s, int e) {s+=mx; e+=mx;int r=0;while(s<=e) {if (s&1) { r+=ix[s]; r%=MOD; s++;}if ((e&1)==0) { r+=ix[e]; r%=MOD; e--; }s>>=1;e>>=1;}return r;}int count(int s, int e) {s+=mx; e+=mx;int r=0;while(s<=e) {if (s&1) { r+=cx[s]; s++;}if ((e&1)==0) { r+=cx[e]; e--; }s>>=1;e>>=1;}return r;}void setv(int i, int v) {int p=i+mx;while(p) {cx[p]+=1; p>>=1;}p=i+mx;while(p) {ix[p]=(ix[p]+v)%MOD; p>>=1;}}int as[200004];int bb[200004];int main() {int n, i;LL r, v, vv, c, t;scanf("%d", &n);bb[0]=1; for (i=1; i<=n; i++) bb[i]=(bb[i-1]*2)%MOD;for (i=0; i<n; i++) scanf("%d", &as[i]);mx=1; while(mx<=n) mx<<=1;memset(ix, 0, sizeof(ix[0])*(mx+mx));memset(cx, 0, sizeof(cx[0])*(mx+mx));r=0;for (i=n-1; i>=0; i--) {v = sumit(0, as[i]-1);c = count(0, as[i]-1);vv = bb[n-i-1]-1; if (vv<0) vv+=MOD;t = vv*c; t%=MOD; t-=v; if (t<0) t+=MOD;t*=bb[i]; t%=MOD;r+=t; r%=MOD;setv(as[i], vv);}printf("%lld\n", r);return 0;}