#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define fi first
#define se second
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define filter(v) v.resize(unique(all(v)) - v.begin())
#define dbg(x) "[" #x << " = " << x << "]"
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> bool maximize(T &a, T b) {
if(a < b) return a = b, true;
else return false;
}
template<typename T> bool minimize(T &a, T b) {
if(a > b) return a = b, true;
else return false;
}
template<typename T1, typename T2> T2 rnd(T1 l, T2 r) {
return uniform_int_distribution<T2>(l, r)(rng);
}
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, int> pli;
typedef pair<long long, long long> pll;
const int N = 4e5 + 3;
const int S = 500;
int n;
int a[N];
int cnt[N];
ll answer = 0;
vector<int> cps;
vector<int> color[N];
void process() {
sort(all(cps)); filter(cps);
for(int i = 1; i <= n; i++) {
a[i] = lower_bound(all(cps), a[i]) - cps.begin() + 1;
color[a[i]].push_back(i);
}
for(int c = 1; c <= n; c++) {
if(sz(color[c]) >= S) {
int prefix = n, total = 0;
fill(cnt, cnt + 1 + 2 * n, 0);
cnt[prefix]++;
for(int i = 1; i <= n; i++) {
int value = (a[i] == c ? 1 : -1);
prefix += value;
if(value == 1) total += cnt[prefix - 1];
else total -= cnt[prefix];
cnt[prefix]++;
answer += total;
}
}
}
fill(cnt, cnt + 1 + n, 0);
for(int i = 1; i <= n; i++) {
int bound = min(n, i + 2 * S - 1), dominate = 0;
for(int j = i; j <= bound; j++) {
if(sz(color[a[j]]) < S) {
cnt[a[j]]++;
maximize(dominate, cnt[a[j]]);
if(dominate >= (j - i + 1) / 2 + 1) answer++;
}
}
for(int j = i; j <= bound; j++) cnt[a[j]] = 0;
}
cout << answer << endl;
}
void input() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
cps.push_back(a[i]);
}
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
#define task "VBAUCU"
if(fopen(task".INP", "r")) {
freopen(task".INP", "r", stdin);
freopen(task".OUT", "w", stdout);
}
int testcase = 1; // cin >> testcase;
for(int i = 1; i <= testcase; i++) {
input();
process();
}
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'int32_t main()':
Main.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | freopen(task".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | freopen(task".OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |