#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 + 1, bruh = 450;
int a[N], n, k;
int cnt[N];
int cnt1[N];
signed main(){
speed;
cin >> n;
vector<pair<int, int>> v;
for(int i = 1; i <= n; i++){
cin >> a[i];
v.pb({a[i], i});
}
sort(all(v));
int prev = -1, cur = 0;
for(auto [x, y] : v){
if(x != prev){
++cur;
prev = x;
a[y] = cur;
cnt[a[y]]++;
}
else a[y] = cur, cnt[a[y]]++;
}
ll ans = 0;
for(int x = 1; x <= cur; x++){
int sz = cnt[x];
if(sz > bruh){
int mp[n * 2 + 1];
for(int i = 0; i < 2 * n + 1; i++) mp[i] = 0;
ll cur = 0LL, act = 0LL;
ans = (0LL + (n * (n + 1LL))) / 2LL;
for(int i = 1; i <= n; i++){
if(a[i] == x) cur--;
else cur++;
mp[cur + n]++;
}
cur = 0;
for(int i = 1; i <= n; i++){
ans -= 0LL + mp[act + n];
if(a[i] == x){
cur--;
act--;
}
else{
cur++;
act++;
}
mp[cur + n]--;
}
}
}
for(int i = 1; i <= n; i++){
memset(cnt1, 0, sizeof(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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
4 ms |
2688 KB |
Output is correct |
4 |
Correct |
4 ms |
2652 KB |
Output is correct |
5 |
Correct |
4 ms |
2692 KB |
Output is correct |
6 |
Correct |
4 ms |
2652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
4 ms |
2688 KB |
Output is correct |
4 |
Correct |
4 ms |
2652 KB |
Output is correct |
5 |
Correct |
4 ms |
2692 KB |
Output is correct |
6 |
Correct |
4 ms |
2652 KB |
Output is correct |
7 |
Correct |
11 ms |
2648 KB |
Output is correct |
8 |
Correct |
2 ms |
2652 KB |
Output is correct |
9 |
Correct |
25 ms |
2652 KB |
Output is correct |
10 |
Correct |
25 ms |
2724 KB |
Output is correct |
11 |
Correct |
26 ms |
2652 KB |
Output is correct |
12 |
Correct |
25 ms |
2652 KB |
Output is correct |
13 |
Correct |
25 ms |
2652 KB |
Output is correct |
14 |
Correct |
25 ms |
2904 KB |
Output is correct |
15 |
Correct |
30 ms |
2652 KB |
Output is correct |
16 |
Correct |
25 ms |
2716 KB |
Output is correct |
17 |
Correct |
26 ms |
2648 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1706 ms |
4820 KB |
Output is correct |
2 |
Correct |
2251 ms |
5528 KB |
Output is correct |
3 |
Correct |
1360 ms |
4364 KB |
Output is correct |
4 |
Correct |
2341 ms |
5588 KB |
Output is correct |
5 |
Correct |
2485 ms |
5832 KB |
Output is correct |
6 |
Correct |
2658 ms |
5892 KB |
Output is correct |
7 |
Correct |
2591 ms |
5828 KB |
Output is correct |
8 |
Correct |
2625 ms |
5828 KB |
Output is correct |
9 |
Correct |
2670 ms |
5844 KB |
Output is correct |
10 |
Correct |
2622 ms |
5828 KB |
Output is correct |
11 |
Correct |
2699 ms |
5844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
4 ms |
2688 KB |
Output is correct |
4 |
Correct |
4 ms |
2652 KB |
Output is correct |
5 |
Correct |
4 ms |
2692 KB |
Output is correct |
6 |
Correct |
4 ms |
2652 KB |
Output is correct |
7 |
Correct |
11 ms |
2648 KB |
Output is correct |
8 |
Correct |
2 ms |
2652 KB |
Output is correct |
9 |
Correct |
25 ms |
2652 KB |
Output is correct |
10 |
Correct |
25 ms |
2724 KB |
Output is correct |
11 |
Correct |
26 ms |
2652 KB |
Output is correct |
12 |
Correct |
25 ms |
2652 KB |
Output is correct |
13 |
Correct |
25 ms |
2652 KB |
Output is correct |
14 |
Correct |
25 ms |
2904 KB |
Output is correct |
15 |
Correct |
30 ms |
2652 KB |
Output is correct |
16 |
Correct |
25 ms |
2716 KB |
Output is correct |
17 |
Correct |
26 ms |
2648 KB |
Output is correct |
18 |
Correct |
1706 ms |
4820 KB |
Output is correct |
19 |
Correct |
2251 ms |
5528 KB |
Output is correct |
20 |
Correct |
1360 ms |
4364 KB |
Output is correct |
21 |
Correct |
2341 ms |
5588 KB |
Output is correct |
22 |
Correct |
2485 ms |
5832 KB |
Output is correct |
23 |
Correct |
2658 ms |
5892 KB |
Output is correct |
24 |
Correct |
2591 ms |
5828 KB |
Output is correct |
25 |
Correct |
2625 ms |
5828 KB |
Output is correct |
26 |
Correct |
2670 ms |
5844 KB |
Output is correct |
27 |
Correct |
2622 ms |
5828 KB |
Output is correct |
28 |
Correct |
2699 ms |
5844 KB |
Output is correct |
29 |
Correct |
2680 ms |
5884 KB |
Output is correct |
30 |
Correct |
484 ms |
3040 KB |
Output is correct |
31 |
Correct |
982 ms |
3548 KB |
Output is correct |
32 |
Correct |
2500 ms |
4568 KB |
Output is correct |
33 |
Correct |
1082 ms |
3548 KB |
Output is correct |
34 |
Correct |
1110 ms |
3548 KB |
Output is correct |
35 |
Correct |
708 ms |
3036 KB |
Output is correct |
36 |
Correct |
436 ms |
3036 KB |
Output is correct |
37 |
Correct |
515 ms |
3040 KB |
Output is correct |
38 |
Incorrect |
2446 ms |
5836 KB |
Output isn't correct |
39 |
Halted |
0 ms |
0 KB |
- |