#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("03, Ofast, unroll-loops")
const int N = 2e5 + 5, T = 20;
bool mark[N];
long long ans;
int n, a[N], cnt[N], seg[N << 1];
inline void readInput();
inline void compress();
inline void pre();
inline void add(int i);
inline int get(int i);
inline long long calc1(int x);
inline long long calc2(int x);
inline void solve();
inline void writeOutput();
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
readInput();
solve();
writeOutput();
return 0;
}
inline void readInput() {
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
}
inline void compress() {
vector<pair<int, int>> v;
for (int i = 0; i < n; i++)
v.push_back({a[i], i});
int tmp = 0;
sort(v.begin(), v.end());
for (int i = 0; i < n - 1; i++)
a[v[i].second] = tmp, tmp += (v[i].first != v[i + 1].first);
a[v[n - 1].second] = tmp;
}
inline void pre() {
compress();
for (int i = 0; i < n; i++)
cnt[a[i]]++;
}
inline void add(int i) {
for (; i <= (n << 1 | 1); i += (i & -i))
seg[i]++;
}
inline int get(int i) {
int res = 0;
for (; i; i -= (i & -i))
res += seg[i];
return res;
}
inline long long calc1(int x) {
long long res = 0;
for (int len = 1; len <= min(2 * cnt[x], n); len++) {
int num = 0;
for (int i = 0; i < n; i++) {
if (i < len)
num += (a[i] == x);
else {
res += ((len / 2) < num);
num += (a[i] == x) - (a[i - len] == x);
}
}
res += ((len / 2) < num);
}
return res;
}
inline long long calc2(int x) {
int sum = 0;
long long res = 0;
memset(seg, 0, sizeof seg);
for (int i = 0; i < n; i++) {
sum += 1 - 2 * (a[i] != x);
res += get(sum + n) + (0 < sum), add(sum + n + 1);
}
return res;
}
inline void solve() {
pre();
for (int i = 0; i < n; i++) {
if (mark[a[i]]) continue;
mark[a[i]] = true;
if (cnt[a[i]] < T)
ans += calc1(a[i]);
else
ans += calc2(a[i]);
}
}
inline void writeOutput() {
cout << ans;
}
Compilation message (stderr)
Main.cpp:4:48: warning: bad option '-f Ofast' to pragma 'optimize' [-Wpragmas]
4 | #pragma GCC optimize ("03, Ofast, unroll-loops")
| ^
Main.cpp:4:48: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
Main.cpp:11:23: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
11 | inline void readInput();
| ^
Main.cpp:11:23: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:11:23: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:11:23: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:12:22: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
12 | inline void compress();
| ^
Main.cpp:12:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:12:22: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:12:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:13:17: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
13 | inline void pre();
| ^
Main.cpp:13:17: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:13:17: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:13:17: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:14:22: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
14 | inline void add(int i);
| ^
Main.cpp:14:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:14:22: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:14:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:15:21: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
15 | inline int get(int i);
| ^
Main.cpp:15:21: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:15:21: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:15:21: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:16:29: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
16 | inline long long calc1(int x);
| ^
Main.cpp:16:29: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:16:29: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:16:29: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:17:29: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
17 | inline long long calc2(int x);
| ^
Main.cpp:17:29: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:17:29: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:17:29: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:18:19: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
18 | inline void solve();
| ^
Main.cpp:18:19: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:18:19: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:18:19: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:19:25: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
19 | inline void writeOutput();
| ^
Main.cpp:19:25: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:19:25: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:19:25: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:21:10: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
21 | int main() {
| ^
Main.cpp:21:10: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:29:23: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
29 | inline void readInput() {
| ^
Main.cpp:29:23: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:35:22: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
35 | inline void compress() {
| ^
Main.cpp:35:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:46:17: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
46 | inline void pre() {
| ^
Main.cpp:46:17: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:52:22: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
52 | inline void add(int i) {
| ^
Main.cpp:52:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:57:21: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
57 | inline int get(int i) {
| ^
Main.cpp:57:21: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:64:29: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
64 | inline long long calc1(int x) {
| ^
Main.cpp:64:29: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:81:29: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
81 | inline long long calc2(int x) {
| ^
Main.cpp:81:29: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:92:19: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
92 | inline void solve() {
| ^
Main.cpp:92:19: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:104:25: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
104 | inline void writeOutput() {
| ^
Main.cpp:104:25: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]| # | 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... |
