結果
問題 | No.2327 Inversion Sum |
ユーザー |
|
提出日時 | 2023-05-28 14:02:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 86 ms / 2,000 ms |
コード長 | 1,492 bytes |
コンパイル時間 | 1,036 ms |
コンパイル使用メモリ | 88,096 KB |
実行使用メモリ | 11,080 KB |
最終ジャッジ日時 | 2024-12-26 23:02:47 |
合計ジャッジ時間 | 2,758 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#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;}