Submission #1224376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224376		vipul	Group Photo (JOI21_ho_t3)	C++20	0 / 100	0 ms	320 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Fenwick {
    int n;
    vector<ll> bit;
    Fenwick(int _n) : n(_n), bit(n + 2, 0) {}
    
    void add(int i, ll v) {
        while (i <= n) {
            bit[i] += v;
            i += i & -i;
        }
    }
    
    ll sum(int i) {
        ll res = 0;
        while (i > 0) {
            res += bit[i];
            i -= i & -i;
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<ll> A(N), B(N);
    
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        B[i] = A[i] + 2LL * i;
    }

    // Coordinate compression
    vector<ll> comp = B;
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());

    int M = comp.size();
    Fenwick fw(M + 2);
    ll ans = 0;

    for (int i = 0; i < N; ++i) {
        int pos = lower_bound(comp.begin(), comp.end(), B[i]) - comp.begin() + 1;
        ans += i - fw.sum(pos);
        fw.add(pos, 1);
    }

    cout << ans << '\n';
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 32
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36