이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
ll sum(ll l, ll r) {
// l^2 + ... + r^2
l--;
return r * (r + 1) / 2 - l * (l + 1) / 2;
return r * (r + 1) * (2 * r + 1) / 6 - l * (l + 1) * (2 * l + 1) / 6;
}
int brute(int n, vector<int> &a) {
int ans = 0;
for (int i = 0; i < n; i++) {
vector<int> cnt(n);
int mx = 0;
for (int j = i; j < n; j++) {
cnt[a[j]]++;
mx = max(mx, cnt[a[j]]);
if (2 * mx > (j - i + 1)) {
ans++;
}
}
}
return ans;
}
void solve() {
int n;
cin >> n;
map<int, int> mp;
vector<int> cnt, a(n);
{
for (int &x: a) {
cin >> x;
mp[x];
}
int z = 0;
for (auto &it: mp) {
it.second = z++;
}
cnt.assign(mp.size(), 0);
for (int &x: a) {
x = mp[x];
cnt[x]++;
}
}
vector<vector<int>> pos(mp.size());
for (int i = 0; i < n; i++) {
pos[a[i]].emplace_back(i);
}
int N = 2000;
ll ans = 0;
for (int i = 0; i < mp.size(); i++) {
if (cnt[i] <= N) {
// cout << i << endl;
for (int l = 0; l < cnt[i]; l++) {
for (int r = l; r < cnt[i]; r++) {
int left = 0, right = n - 1, plus = r - l + 1;
int have = 2 * plus - (pos[i][r] - pos[i][l] + 1);
ll now = 0;
if (have <= 0) {
continue;
}
if (l > 0) {
left = pos[i][l - 1] + 1;
}
if (r + 1 < cnt[i]) {
right = pos[i][r + 1] - 1;
}
right = min(right, pos[i][r] + (have - 1));
left = max(left, pos[i][l] - (have - 1));
int right2 = left + (2 * plus - 1) - 1;
int left2 = right - (2 * plus - 1) + 1;
// cout << l << ' ' << r << ' ' << left << ' ' << right << ' ' << right2 << ' ';
if (right2 < right) {
int x = pos[i][l] - left2 + 1;
now += sum(x, right - right2 + x - 1);
} else {
right2 = right;
}
now += (pos[i][l] - left + 1) * (right2 - pos[i][r] + 1);
// cout << '\t' << now << endl;
ans += now;
// right - 1
// right-1 - 2
// ...
// right2 - da stop
// qogani bir hil
}
}
}
// cout << "\t\t" << ans << endl;
}
#ifdef test_cases
cout << brute(n, a) << '\n';
#endif
cout << ans;
}
int main() {
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
int queries = 1;
#ifdef test_cases
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin >> queries;
#else
// cin >> queries;
#endif
for (int test_case = 1; test_case <= queries; test_case++) {
#ifdef test_cases
cout << "Test case: " << test_case << '\n';
#endif
solve();
cout << '\n';
}
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'void solve()':
Main.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int i = 0; i < mp.size(); i++) {
| ~~^~~~~~~~~~~
# | 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... |