제출 #1224363

#제출 시각아이디문제언어결과실행 시간메모리
1224363vipulGroup Photo (JOI21_ho_t3)C++20
0 / 100
0 ms320 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; struct Fenwick { int n; vector<ll> f; Fenwick(int _n): n(_n), f(n+1, 0) {} void update(int i, ll v) { for (; i <= n; i += i&-i) f[i] += v; } ll query(int i) { ll s = 0; for (; i > 0; i -= i&-i) s += f[i]; return s; } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<ll> B(N); for(int i = 0; i < N; i++){ ll a; cin >> a; B[i] = a + 2LL * i; } // Coordinate‐compress B so we can index the Fenwick tree vector<ll> vals = B; sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); Fenwick fw(vals.size()); ll ans = 0; // We iterate left-to-right; at each B[i], we want // # of previous B[j] > B[i] = total_seen - # of previous ≤ B[i] for(int i = 0; i < N; i++){ int pos = int(lower_bound(vals.begin(), vals.end(), B[i]) - vals.begin()) + 1; ll seen_le = fw.query(pos); ll seen_tot = i; ans += (seen_tot - seen_le); fw.update(pos, 1); } cout << ans << "\n"; return 0; }
#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...