This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |