# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1224402 | vipul | Group Photo (JOI21_ho_t3) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct BIT {
vector<ll> bit; // Use ll instead of int to prevent overflow
int n;
BIT(int n) {
this->n = n;
bit.assign(n + 2, 0);
}
void add(int idx, ll val) {
while (idx <= n) {
bit[idx] += val;
idx += idx & -idx;
}
}
ll sum(int idx) {
ll res = 0;
while (idx > 0) {
res += bit[idx];
idx -= idx & -idx;
}
return res;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<ll> A(N), T(N);
for (int i = 0; i < N; ++i) {
cin >> A[i];
T[i] = A[i] - 2LL * i;
}
vector<ll> comp = T;
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
BIT bit(comp.size() + 2);
ll ans = 0;
for (int i = N - 1; i >= 0; --i) {