Submission #1224405

#TimeUsernameProblemLanguageResultExecution timeMemory
1224405vipulGroup Photo (JOI21_ho_t3)C++20
0 / 100
0 ms320 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; struct BIT { vector<ll> bit; 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) { int pos = lower_bound(comp.begin(), comp.end(), T[i]) - comp.begin() + 1; ans += bit.sum(pos - 1); bit.add(pos, 1); } cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...