Submission #764858

#TimeUsernameProblemLanguageResultExecution timeMemory
764858drdilyorIzbori (COCI22_izbori)C++17
40 / 110
3058 ms5324 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; constexpr int inf = 1e9; constexpr ll infl = 1e18; struct Fenwick { int n; vector<int> tree; Fenwick() = default; Fenwick(int n) : n(n), tree(n) {} int sum(int r) { int s = 0; for (; r >= 0; r = (r&(r+1))-1) s+= tree[r]; return s; } void inc(int i, int d=1) { for (; i < n; i |= i+1) tree[i] += d; } }; int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; vector<int> arr(n); for (int& i : arr) cin >> i; set<int> poss(arr.begin(), arr.end()); ll cnt = 0; for (int x : poss) { vector<int> brr(n+1); brr[0] = n; for (int i = 0; i < n; i++){ brr[i+1] = brr[i] + (arr[i] == x ? 1 : -1); } Fenwick t(n*2+1); t.inc(brr[0]); for (int i = 1; i <= n; i++) { cnt += t.sum(brr[i]-1); t.inc(brr[i]); } } cout << cnt << '\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...