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 <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <functional>
#include <complex>
#include <climits>
#include <random>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
using namespace std;
#define pb push_back
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define speed ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
const int mod = (int) 1e9 + 7;
const int N = (int) 2e5 + 100, bruh = 500;
ll a[N], n, k;
map<int, int> cnt;
signed main(){
speed;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
cnt[a[i]]++;
}
ll ans = 0;
for(auto [x, sz] : cnt){
if(sz > bruh){
map <ll, ll> mp;
ll cur = 0, act = 0;
ans = (1LL * (n * (n + 1))) / 2LL;
for(ll i = 1; i <= n; i++){
if(a[i] == x) cur--;
else cur++;
mp[cur]++;
}
cur = 0;
for(ll i = 1; i <= n; i++){
ans -= mp[act];
if(a[i] == x){
cur--;
act--;
}
else{
cur++;
act++;
}
mp[cur]--;
}
}
}
for(int i = 1; i <= n; i++){
map<int, int> cnt1;
int lst = -1, lstA = -1;
for(int j = i; j <= n; j++){
if((j - i + 1) > 2 * bruh) break;
if(a[j] == lstA) lst++;
++cnt1[a[j]];
int sz = (j - i) + 1;
if(lst > (sz / 2) && cnt[lstA] <= bruh) ans++;
else if(cnt1[a[j]] > (sz / 2) && cnt[a[j]] <= bruh){
ans++;
lst = cnt1[a[j]];
lstA = a[j];
}
}
}
cout << ans;
}
# | 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... |