結果
問題 | No.2327 Inversion Sum |
ユーザー |
![]() |
提出日時 | 2023-05-28 14:02:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 76 ms / 2,000 ms |
コード長 | 1,315 bytes |
コンパイル時間 | 4,296 ms |
コンパイル使用メモリ | 261,448 KB |
最終ジャッジ日時 | 2025-02-13 10:40:24 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 4000000000000000001 int main(){ int N,M; cin>>N>>M; vector<pair<int,int>> t(M); rep(i,M){ cin>>t[i].second>>t[i].first; } sort(t.begin(),t.end()); fenwick_tree<mint> F(N+1); mint ans = 0; rep(i,M){ ans += F.sum(t[i].second,N+1); F.add(t[i].second,1); } if(N!=M){ vector<int> vs; rep(i,M)vs.push_back(t[i].second); sort(vs.begin(),vs.end()); rep(i,M){ mint tt = distance(upper_bound(vs.begin(),vs.end(),t[i].second),vs.end()); tt = (N-t[i].second) - tt; tt /= N-M; tt *= t[i].first-1-i; ans += tt; } reverse(t.begin(),t.end()); rep(i,t.size()){ t[i].first = N+1-t[i].first; t[i].second = N+1-t[i].second; } rep(i,vs.size()){ vs[i] = N+1-vs[i]; } sort(vs.begin(),vs.end()); rep(i,M){ mint tt = distance(upper_bound(vs.begin(),vs.end(),t[i].second),vs.end()); tt = (N-t[i].second) - tt; tt /= N-M; tt *= t[i].first-1-i; ans += tt; } { mint cur = N-M; cur *= N-M-1; cur /= 2; cur /= 2; ans += cur; } } rep(i,N-M){ ans *= i+1; } cout<<ans.val()<<endl; return 0; }