結果
問題 | No.2327 Inversion Sum |
ユーザー | kotatsugame |
提出日時 | 2023-05-28 14:02:56 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 82 ms / 2,000 ms |
コード長 | 1,492 bytes |
コンパイル時間 | 1,075 ms |
コンパイル使用メモリ | 84,152 KB |
実行使用メモリ | 10,944 KB |
最終ジャッジ日時 | 2023-08-27 08:53:27 |
合計ジャッジ時間 | 3,442 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 15 ms
10,944 KB |
testcase_01 | AC | 73 ms
7,856 KB |
testcase_02 | AC | 58 ms
10,340 KB |
testcase_03 | AC | 12 ms
10,472 KB |
testcase_04 | AC | 82 ms
7,084 KB |
testcase_05 | AC | 14 ms
6,568 KB |
testcase_06 | AC | 56 ms
7,856 KB |
testcase_07 | AC | 30 ms
4,416 KB |
testcase_08 | AC | 11 ms
4,376 KB |
testcase_09 | AC | 73 ms
7,612 KB |
testcase_10 | AC | 19 ms
4,376 KB |
testcase_11 | AC | 5 ms
6,892 KB |
testcase_12 | AC | 5 ms
6,328 KB |
testcase_13 | AC | 2 ms
4,380 KB |
testcase_14 | AC | 46 ms
5,376 KB |
testcase_15 | AC | 76 ms
5,800 KB |
testcase_16 | AC | 32 ms
10,096 KB |
testcase_17 | AC | 8 ms
7,660 KB |
testcase_18 | AC | 10 ms
4,376 KB |
testcase_19 | AC | 25 ms
10,276 KB |
testcase_20 | AC | 2 ms
4,376 KB |
testcase_21 | AC | 1 ms
4,380 KB |
testcase_22 | AC | 2 ms
4,376 KB |
testcase_23 | AC | 2 ms
4,376 KB |
testcase_24 | AC | 1 ms
4,376 KB |
testcase_25 | AC | 1 ms
4,376 KB |
testcase_26 | AC | 2 ms
4,380 KB |
testcase_27 | AC | 1 ms
4,376 KB |
testcase_28 | AC | 1 ms
4,380 KB |
testcase_29 | AC | 1 ms
4,380 KB |
testcase_30 | AC | 1 ms
4,376 KB |
testcase_31 | AC | 2 ms
4,376 KB |
testcase_32 | AC | 1 ms
4,376 KB |
ソースコード
#include<iostream> #include<atcoder/modint> #include<atcoder/lazysegtree> #include<atcoder/fenwicktree> using namespace std; using mint=atcoder::modint998244353; struct dat{ int l,r; long sum; }; dat op(dat x,dat y) { if(x.sum<0)return y; if(y.sum<0)return x; x.r=y.r; x.sum+=y.sum; return x; } dat e(){return{-1,-1,-1};} dat mp(int f,dat x) { x.sum+=(long)f*(x.r-x.l); return x; } int cmp(int f,int g){return f+g;} int id(){return 0;} int N,M; int P[1<<17]; bool ex[1<<17]; int inv[1<<17]; int main() { cin>>N>>M; for(int i=0;i<N;i++)P[i]=-1; for(int i=0;i<M;i++) { int p,k;cin>>p>>k; P[k-1]=p-1; ex[p-1]=true; inv[p-1]=k-1; } vector<int>emp; atcoder::fenwick_tree<int>BIT(N); mint A1=0; for(int i=0;i<N;i++) { if(P[i]==-1)emp.push_back(i); else { A1+=BIT.sum(P[i],N); BIT.add(P[i],1); } } mint coef=1; for(int i=1;i<emp.size();i++)coef*=mint::raw(i); if(!emp.empty()) { A1*=coef*emp.size(); } mint A3=0; if(emp.size()>=2) { mint n=emp.size(); mint t=coef*n; A3=t*n*(n-1)/4; } vector<dat>init(emp.size()); for(int i=0;i<emp.size();i++) { init[i].l=i; init[i].r=i+1; init[i].sum=emp[i]-i; } atcoder::lazy_segtree<dat,op,e,int,mp,cmp,id>seg(init); mint A2=0; for(int i=0;i<N;i++) { if(ex[i]) { int id=inv[i]; id=lower_bound(emp.begin(),emp.end(),id)-emp.begin(); seg.apply(0,id,1); seg.apply(id,emp.size(),-1); } else { A2+=seg.all_prod().sum; } } A2*=coef; cout<<(A1+A2+A3).val()<<endl; }