結果

問題 No.2327 Inversion Sum
ユーザー 👑 NachiaNachia
提出日時 2023-05-28 14:55:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,863 bytes
コンパイル時間 1,009 ms
コンパイル使用メモリ 88,432 KB
最終ジャッジ日時 2025-02-13 12:15:07
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 29 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#line 2 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\array\\fenwicktree-atcoder.hpp"
#include <cassert>
#include <vector>
namespace nachia {
template <class T> struct FenwickTree {
public:
FenwickTree() : _n(0){}
explicit FenwickTree(int n, T ZERO) : _n(n), a(n, ZERO){}
void add(int p, T x){
assert(0 <= p && p < _n);
p++;
while(p <= _n){
a[p-1] += T(x);
p += p & -p;
}
}
T sum(int r){
assert(0 <= r && r <= _n);
return sumr(r);
}
T sum(int l, int r){
assert(0 <= l && l <= r && r <= _n);
return sumr(r) - sumr(l);
}
private:
int _n;
std::vector<T> a;
T sumr(int r){
T s = 0;
while(r > 0){
s += a[r-1];
r -= r & -r;
}
return s;
}
};
} // namespace nachia
#line 3 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\range-query\\point-add-range-sum.hpp"
namespace nachia {
template<class T> using PointAddRangeSum = FenwickTree<T>;
} // namespace nachia
#line 3 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\array\\coordinate-compress.hpp"
#include <algorithm>
namespace nachia{
template<class Elem>
class CoordinateCompress {
std::vector<Elem> G;
std::vector<int> res;
std::vector<int> resinv;
std::vector<Elem> mRealval;
Elem mMaxcoord;
bool ok = true;
void calc() {
if (ok) return;
int n = G.size();
resinv.resize(n);
for(int i=0; i<n; i++) resinv[i] = i;
sort(resinv.begin(), resinv.end(), [this](int l, int r) -> bool { return G[l] < G[r]; });
res.resize(n);
mRealval.clear();
int p = 0;
res[resinv[0]] = p;
mRealval.push_back(G[resinv[0]]);
for(int i=1; i<n; i++){
if(G[resinv[i-1]] < G[resinv[i]]){ mRealval.push_back(G[resinv[i]]); p++; }
res[resinv[i]] = p;
}
mMaxcoord = p;
ok = true;
}
public:
int push(Elem x) {
ok = false;
int p = G.size();
G.push_back(x);
return p;
}
int operator[](int i) {
calc();
return res[i];
}
Elem realval(int x) {
calc();
return mRealval[x];
}
Elem maxcoord() {
calc();
return mMaxcoord;
}
};
template<class Elem>
std::vector<int> CoordinateCompressInstant(const std::vector<Elem>& A, bool disjoint = false){
int n = A.size();
std::vector<int> ord(n);
for(int i=0; i<n; i++) ord[i] = i;
if(disjoint){
std::sort(ord.begin(), ord.end(), [&](int l, int r) -> bool { return (A[l] != A[r]) ? (A[l] < A[r]) : (l < r); });
std::vector<int> res(n, 0);
for(int i=0; i<n; i++) res[ord[i]] = i;
return res;
}
std::sort(ord.begin(), ord.end(), [&](int l, int r) -> bool { return A[l] < A[r]; });
std::vector<int> res(n, 0);
for(int i=1; i<n; i++) res[ord[i]] = res[ord[i-1]] + ((A[ord[i-1]] < A[ord[i]]) ? 1 : 0);
return res;
}
} // namespace nachia
#line 6 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\array\\inversion.hpp"
namespace nachia{
// x must be coord-compressed enough
long long Inversion(std::vector<int> x){
if(x.empty()) return 0;
int N = 1 + *std::max_element(x.begin(), x.end());
nachia::PointAddRangeSum<int> rs(N, 0);
long long ans = 0;
for(int a : x){
if(a+1 != N) ans += rs.sum(a+1, N);
rs.add(a, 1);
}
return ans;
}
} // namespace nachia
#line 2 "..\\Main.cpp"
#include <iostream>
#include <string>
#line 6 "..\\Main.cpp"
#include <atcoder/modint>
using namespace std;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
const i64 INF = 1001001001001001001;
using Modint = atcoder::static_modint<998244353>;
int main(){
int N, M; cin >> N >> M;
vector<pair<int,int>> PK(M);
rep(i,M){
int p, k; cin >> p >> k; p--; k--;
PK[i] = { p, k };
}
sort(PK.begin(), PK.end());
vector<int> K;
for(auto a : PK) K.push_back(a.second);
Modint f = 1;
for(int i=1; i<=N-M; i++) f *= i;
vector<int> ck(N+1, 1); ck[0] = 0;
vector<int> cp(N+1, 1); cp[0] = 0;
for(auto [p,k] : PK){ ck[k+1]--; cp[p+1]--; }
rep(i,N) ck[i+1] += ck[i];
rep(i,N) cp[i+1] += cp[i];
if(N == M){ cout << f.val() << endl; return 0; }
Modint q = 0;
for(auto [p,k] : PK) q += Modint(cp[p]) * (ck[N] - ck[k]);
for(auto [p,k] : PK) q += Modint(cp[N] - cp[p]) * (ck[k]);
q /= (N-M);
q += Modint(N-M) * Modint(N-M-1) / 4;
q += nachia::Inversion(K);
q *= f;
cout << q.val() << endl;
return 0;
}
struct ios_do_not_sync{
ios_do_not_sync(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
} ios_do_not_sync_instance;
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0