| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 536633 | 2022-03-13T15:44:01 Z | Farhan_HY | Izbori (COCI22_izbori) | C++14 | 258 ms | 18008 KB |
#include <bits/stdc++.h>
#define int long long
#define float double
#define pb push_back
#define F first
#define S second
#define T int t; cin >> t; while(t--)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int inf = 8e18;
const int N = 1e6 + 6;
const int M = 1e3 + 3;
const int LOG = 31;
const int mod = 1e9 + 7;
const float pi = atan(1) * 4;
int n, a[N], pre[N];
map<int, int> cnt;
multiset<int> st;
main()
{
IOS
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
if (n <= 2000)
{
int Ans = 0;
for(int i = 1; i <= n; i++)
{
for(int j = i; j <= n; j++)
{
if (cnt[a[j]] != 0)
st.erase(st.find(cnt[a[j]]));
st.insert(++cnt[a[j]]);
Ans += (*st.rbegin() > (j - i + 1) / 2);
}
cnt.clear();
st.clear();
}
cout << Ans;
}
else
{
for(int i = 1; i <= n; i++)
{
if (a[i] == 2)
pre[i] = pre[i - 1] - 1;
else
pre[i] = pre[i - 1] + 1;
cnt[pre[i]]++;
}
int Ans = n * (n + 1) / 2;
for(int i = 1; i <= n; i++)
{
Ans -= cnt[pre[i - 1]];
cnt[pre[i]]--;
}
cout << Ans;
}
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 212 KB | Output is correct |
| 2 | Correct | 1 ms | 340 KB | Output is correct |
| 3 | Correct | 4 ms | 340 KB | Output is correct |
| 4 | Correct | 4 ms | 212 KB | Output is correct |
| 5 | Correct | 4 ms | 340 KB | Output is correct |
| 6 | Correct | 3 ms | 340 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 212 KB | Output is correct |
| 2 | Correct | 1 ms | 340 KB | Output is correct |
| 3 | Correct | 4 ms | 340 KB | Output is correct |
| 4 | Correct | 4 ms | 212 KB | Output is correct |
| 5 | Correct | 4 ms | 340 KB | Output is correct |
| 6 | Correct | 3 ms | 340 KB | Output is correct |
| 7 | Correct | 108 ms | 428 KB | Output is correct |
| 8 | Correct | 3 ms | 340 KB | Output is correct |
| 9 | Correct | 257 ms | 360 KB | Output is correct |
| 10 | Correct | 247 ms | 340 KB | Output is correct |
| 11 | Correct | 258 ms | 356 KB | Output is correct |
| 12 | Correct | 250 ms | 352 KB | Output is correct |
| 13 | Correct | 250 ms | 340 KB | Output is correct |
| 14 | Correct | 235 ms | 352 KB | Output is correct |
| 15 | Correct | 251 ms | 352 KB | Output is correct |
| 16 | Correct | 246 ms | 352 KB | Output is correct |
| 17 | Correct | 90 ms | 340 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 15 ms | 2388 KB | Output is correct |
| 2 | Correct | 17 ms | 3028 KB | Output is correct |
| 3 | Correct | 15 ms | 1872 KB | Output is correct |
| 4 | Correct | 25 ms | 3176 KB | Output is correct |
| 5 | Correct | 19 ms | 3224 KB | Output is correct |
| 6 | Correct | 23 ms | 3540 KB | Output is correct |
| 7 | Correct | 23 ms | 3480 KB | Output is correct |
| 8 | Correct | 28 ms | 3524 KB | Output is correct |
| 9 | Correct | 22 ms | 3520 KB | Output is correct |
| 10 | Correct | 22 ms | 3424 KB | Output is correct |
| 11 | Correct | 88 ms | 15964 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 212 KB | Output is correct |
| 2 | Correct | 1 ms | 340 KB | Output is correct |
| 3 | Correct | 4 ms | 340 KB | Output is correct |
| 4 | Correct | 4 ms | 212 KB | Output is correct |
| 5 | Correct | 4 ms | 340 KB | Output is correct |
| 6 | Correct | 3 ms | 340 KB | Output is correct |
| 7 | Correct | 108 ms | 428 KB | Output is correct |
| 8 | Correct | 3 ms | 340 KB | Output is correct |
| 9 | Correct | 257 ms | 360 KB | Output is correct |
| 10 | Correct | 247 ms | 340 KB | Output is correct |
| 11 | Correct | 258 ms | 356 KB | Output is correct |
| 12 | Correct | 250 ms | 352 KB | Output is correct |
| 13 | Correct | 250 ms | 340 KB | Output is correct |
| 14 | Correct | 235 ms | 352 KB | Output is correct |
| 15 | Correct | 251 ms | 352 KB | Output is correct |
| 16 | Correct | 246 ms | 352 KB | Output is correct |
| 17 | Correct | 90 ms | 340 KB | Output is correct |
| 18 | Correct | 15 ms | 2388 KB | Output is correct |
| 19 | Correct | 17 ms | 3028 KB | Output is correct |
| 20 | Correct | 15 ms | 1872 KB | Output is correct |
| 21 | Correct | 25 ms | 3176 KB | Output is correct |
| 22 | Correct | 19 ms | 3224 KB | Output is correct |
| 23 | Correct | 23 ms | 3540 KB | Output is correct |
| 24 | Correct | 23 ms | 3480 KB | Output is correct |
| 25 | Correct | 28 ms | 3524 KB | Output is correct |
| 26 | Correct | 22 ms | 3520 KB | Output is correct |
| 27 | Correct | 22 ms | 3424 KB | Output is correct |
| 28 | Correct | 88 ms | 15964 KB | Output is correct |
| 29 | Correct | 110 ms | 18008 KB | Output is correct |
| 30 | Incorrect | 17 ms | 3548 KB | Output isn't correct |
| 31 | Halted | 0 ms | 0 KB | - |