結果
問題 | No.2327 Inversion Sum |
ユーザー |
![]() |
提出日時 | 2023-05-28 14:03:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 50 ms / 2,000 ms |
コード長 | 1,569 bytes |
コンパイル時間 | 4,300 ms |
コンパイル使用メモリ | 230,760 KB |
実行使用メモリ | 6,132 KB |
最終ジャッジ日時 | 2024-12-26 23:08:41 |
合計ジャッジ時間 | 5,977 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
// g++ 1.cpp -std=c++17 -O2 -I . #include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll = long long; using ld = long double; using vi = vector<int>; using vvi = vector<vi>; using vll = vector<ll>; using vvll = vector<vll>; using vld = vector<ld>; using vvld = vector<vld>; using vst = vector<string>; using vvst = vector<vst>; #define fi first #define se second #define pb push_back #define eb emplace_back #define pq_big(T) priority_queue<T,vector<T>,less<T>> #define pq_small(T) priority_queue<T,vector<T>,greater<T>> #define all(a) a.begin(),a.end() #define rep(i,start,end) for(ll i=start;i<(ll)(end);i++) #define per(i,start,end) for(ll i=start;i>=(ll)(end);i--) #define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end()) using mint = modint998244353; int op(int a,int b){ return (int)a+b; } int e(){ return 0; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll n,k;cin>>n>>k; mint ans=0; ans=((n-k)*(n-k-1)); ans/=4; vi v(n,-1),x(n,1); rep(i,0,k){ int p,q;cin>>p>>q; p--;q--; v[q]=p; x[p]=0; } mint now=0; segtree<int,op,e> seg(n),seg2(x); per(i,n-1,0){ if(v[i]==-1){ ans+=now; // ? - fix } else{ ans+=seg.prod(0,v[i]); seg.set(v[i],1); if((n-k)!=0)now+=(mint)seg2.prod(v[i],n)/(n-k); } } now=0; rep(i,0,n){ if(v[i]==-1){ ans+=now; // fix - ? } else{ if((n-k)!=0)now+=(mint)seg2.prod(0,v[i])/(n-k); } } rep(i,0,n-k){ ans*=i+1; } cout<<ans.val()<<endl; }