結果

問題 No.2327 Inversion Sum
ユーザー 👑 NachiaNachia
提出日時 2023-05-28 14:55:31
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,863 bytes
コンパイル時間 1,119 ms
コンパイル使用メモリ 89,736 KB
実行使用メモリ 5,296 KB
最終ジャッジ日時 2023-08-27 10:53:42
合計ジャッジ時間 2,458 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
4,416 KB
testcase_01 AC 17 ms
5,296 KB
testcase_02 AC 12 ms
4,728 KB
testcase_03 AC 4 ms
4,380 KB
testcase_04 AC 19 ms
4,972 KB
testcase_05 AC 4 ms
4,380 KB
testcase_06 AC 13 ms
4,852 KB
testcase_07 AC 9 ms
4,384 KB
testcase_08 AC 4 ms
4,376 KB
testcase_09 AC 17 ms
4,792 KB
testcase_10 AC 6 ms
4,380 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 12 ms
4,380 KB
testcase_15 AC 18 ms
4,844 KB
testcase_16 AC 8 ms
4,424 KB
testcase_17 AC 3 ms
4,380 KB
testcase_18 AC 3 ms
4,380 KB
testcase_19 AC 6 ms
4,380 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 2 ms
4,380 KB
testcase_22 AC 2 ms
4,380 KB
testcase_23 AC 1 ms
4,376 KB
testcase_24 WA -
testcase_25 AC 1 ms
4,376 KB
testcase_26 AC 2 ms
4,380 KB
testcase_27 AC 1 ms
4,380 KB
testcase_28 AC 1 ms
4,380 KB
testcase_29 AC 2 ms
4,384 KB
testcase_30 AC 1 ms
4,380 KB
testcase_31 AC 1 ms
4,376 KB
testcase_32 AC 2 ms
4,384 KB
権限があれば一括ダウンロードができます

ソースコード

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;
0