#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 100;
#define int long long
vector<int> A, cc, occ[MAXN];
signed main() {
fast;
int n;
cin >> n;
A = vector<int>(n+1);
for (int i = 1; i <= n; i++) {
cin >> A[i];
cc.push_back(A[i]);
}
sort(cc.begin(), cc.end());
cc.erase(unique(cc.begin(), cc.end()), cc.end());
int N = cc.size();
for (int i = 1; i <= n; i++) {
A[i] = upper_bound(cc.begin(), cc.end(), A[i]) - cc.begin();
occ[A[i]].push_back(i);
}
int cnt = 0;
for (int i = 1; i <= N; i++) {
if (occ[i].size() <= 2000) {
for (int a = 0; a < occ[i].size(); a++) {
for (int b = a; b < occ[i].size(); b++) {
int positive = b - a + 1;
int now = - (occ[i][b] - occ[i][a] + 1) + 2 * positive - 1;
if (now <= 0)
continue;
int left = (a == 0 ? occ[i][a] - 1 : occ[i][a] - occ[i][a-1] - 1);
int right = (b + 1 == occ[i].size() ? n - occ[i][b] : occ[i][b+1] - occ[i][b] - 1);
left = min(left, now);
right = min(right, now);
if (left > right)
swap(left, right);
if (left + right <= now)
cnt += (left + 1) * (right + 1);
else {
cnt += (right + 1) * (right + 2) / 2 + (now - right) * (right + 1);
cnt -= (now - left) * (now - left + 1) / 2;
}
}
}
} else {
}
}
cout << cnt << "\n";
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:38:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (int a = 0; a < occ[i].size(); a++) {
| ~~^~~~~~~~~~~~~~~
Main.cpp:39:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for (int b = a; b < occ[i].size(); b++) {
| ~~^~~~~~~~~~~~~~~
Main.cpp:47:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | int right = (b + 1 == occ[i].size() ? n - occ[i][b] : occ[i][b+1] - occ[i][b] - 1);
| ~~~~~~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
4952 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
4952 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
13 ms |
9428 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
4952 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |