Submission #972260

#TimeUsernameProblemLanguageResultExecution timeMemory
972260RandomUserIzbori (COCI22_izbori)C++17
25 / 110
13 ms2392 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt") struct BIT { int n; vector<int> tree; BIT(int _n) { n = _n + 10; tree.resize(_n+60); } void update(int p, int v) { for(p++; p<n; p+=p&-p) tree[p] += v; } int query(int p) { int ans = 0; for(p++; p>0; p-=p&-p) ans += tree[p]; return ans; } int query(int l, int r) { return query(r) - query(l-1); } void reset(int p) { for(int i=0; i<=p; i++) tree[i] = 0; } }; int main() { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); int n; ll ans = 0; cin >> n; int B = sqrt(n); vector<int> v(n+1), comp; map<int, int> cnt; for(int i=1; i<=n; i++) { cin >> v[i]; if(++cnt[v[i]] == 1) comp.push_back(v[i]); } BIT bit(3*n); for(int &x : comp) { if(cnt[x] >= B) { int sum = 0, mx = n + 1; bit.update(n+1, 1); for(int i=1; i<=n; i++) { sum += (v[i] == x); ans += bit.query(2*sum - i - 1 + (n + 1)); bit.update(2*sum - i + (n + 1), 1); mx = max(mx, 2*sum - i + (n + 1)); } bit.reset(mx); } else { ans += cnt[x]; vector<int> p; p.push_back(0); for(int i=1; i<=n; i++) if(v[i] == x) p.push_back(i); p.push_back(n+1); for(int i=1; i<p.size()-1; i++) { for(int j=i+1; j<p.size()-1; j++) { if(2 * (j - i + 1) <= p[j] - p[i] + 1) continue; int left = 2 * (j - i + 1) - (p[j] - p[i] + 1) - 1; int L = min(left, p[i] - p[i-1] - 1); int R = p[j+1] - p[j] - 1; //for(int k=0; k<=L; k++) ans += min(R, left - k); ans += L + 1; if(left < R) { ans += 1ll * left * (left + 1) / 2; } else { ans += R * (left - R + 1); ans += 1ll * (R - 1) * R / 2; } } } } } cout << ans << '\n'; return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:67:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             for(int i=1; i<p.size()-1; i++) {
      |                          ~^~~~~~~~~~~
Main.cpp:68:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |                 for(int j=i+1; j<p.size()-1; j++) {
      |                                ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...