Submission #74681756

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class ft {
private:
    vector<int> tree;
    int n;
public:
    ft(int size) : n(size), tree(size + 2, 0) {}
    void update(int pos, int delta) {
        for (; pos <= n; pos += pos & -pos) {
            tree[pos] += delta;
        }
    }
    int query(int pos) {
        int res = 0;
        for (; pos > 0; pos -= pos & -pos) {
            res += tree[pos];
        }
        return res;
    }
    void clear() {
        fill(tree.begin(), tree.end(), 0);
    }
};
long long calc(int X, const vector<int>& P, int N) {
    ft ft(N);
    int l = 1;
    long long inv_count = 0;
    long long res = 0;
    for (int r = 1; r <= N; ++r) {
        int x = P[r];
        int add = (r - l) - ft.query(x);
        inv_count += add;
        ft.update(x, 1);
        while (inv_count > X && l <= r) {
            int y = P[l];
            int del = ft.query(y - 1);
            inv_count -= del;
            ft.update(y, -1);
            l++;
        }
        res += r - l + 1;
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K;
    cin >> N >> K;
    vector<int> P(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> P[i];
    }
    long long ans = calc(K, P, N);
    if (K > 0) {
        ans -= calc(K - 1, P, N);
    }
    cout << ans;
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In constructor 'ft::ft(int)':
./Main.cpp:8:9: warning: 'ft::n' will be initialized after [-Wreorder]
    8 |     int n;
      |         ^
./Main.cpp:7:17: warning:   'std::vector<int> ft::tree' [-Wreorder]
    7 |     vector<int> tree;
      |                 ^~~~
./Main.cpp:10:5: warning:   when initialized here [-Wreorder]
   10 |     ft(int size) : n(size), tree(size + 2, 0) {}
      |     ^~

Judge Result