이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int M = 2 * N;
const int B = sqrt(N * 1.87);
int n, a[N], c[M], cnt[N], occ[N];
void modify(int p, int v) {
for (p += N; p < M; p += p & -p) c[p] += v;
}
int query(int p) {
int res = 0;
for (p += N; p > 0; p -= p & -p) res += c[p];
return res;
}
void compress() {
vector<int> xs;
for (int i = 1; i <= n; i++)
xs.push_back(a[i]);
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
for (int i = 1; i <= n; i++) {
a[i] = (int) (lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin()) + 1;
}
}
int readint() {
char c = getchar();
while (c < '0' || c > '9')
c = getchar();
int x = 0;
while ('0' <= c && c <= '9')
x = x * 10 + c - '0', c = getchar();
return x;
}
int main() {
n = readint();
for (int i = 1; i <= n; i++) {
a[i] = readint();
}
compress();
for (int i = 1; i <= n; i++) {
occ[a[i]] += 1;
}
long long ans = 0;
for (int v = 1; v <= n; v++) {
if (occ[v] >= B) {
modify(0, +1);
int bal = 0;
for (int i = 1; i <= n; i++) {
bal += (a[i] == v ? 1 : -1);
ans += query(bal - 1);
modify(bal, +1);
}
modify(0, -1);
bal = 0;
for (int i = 1; i <= n; i++) {
bal += (a[i] == v ? 1 : -1);
modify(bal, -1);
}
}
}
for (int l = 1; l <= n; l++) {
int f = a[l];
for (int r = l; r <= min(l + 2 * B, n); r++) {
cnt[a[r]] += 1;
if (cnt[a[r]] > cnt[f])
f = a[r];
if (cnt[f] * 2 > r - l + 1 && occ[f] < B)
ans++;
}
for (int r = l; r <= min(l + 2 * B, n); r++) {
cnt[a[r]] = 0;
}
}
printf("%lld", ans);
return 0;
}
# | 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... |