Submission #971374

#TimeUsernameProblemLanguageResultExecution timeMemory
971374RandomUserIzbori (COCI22_izbori)C++17
40 / 110
3062 ms4820 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; #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() { for(int &x : tree) x = 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; 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); } bit.reset(); } 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 = p[i] - p[i-1] - 1; int R = p[j+1] - p[j] - 1; for(int k=0; k<=min(L,left); k++) ans += min(R, left - k) + 1; } } } } cout << ans << '\n'; return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             for(int i=1; i<p.size()-1; i++) {
      |                          ~^~~~~~~~~~~
Main.cpp:69:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |                 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...