oj.uz

Submission #536632

# Submission time Handle Problem Language Result Execution time Memory
536632 2022-03-13T15:43:16 Z Farhan_HY Izbori (COCI22_izbori) C++14
25 / 110
 90 ms 16308 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 <= 300)
    {
        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

Main.cpp:22:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   22 | main()
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 6 ms 328 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 6 ms 340 KB Output is correct
6 Correct 3 ms 344 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 6 ms 328 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 6 ms 340 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2644 KB Output is correct
2 Correct 18 ms 3400 KB Output is correct
3 Correct 11 ms 2132 KB Output is correct
4 Correct 20 ms 3596 KB Output is correct
5 Correct 26 ms 3788 KB Output is correct
6 Correct 32 ms 3916 KB Output is correct
7 Correct 29 ms 3796 KB Output is correct
8 Correct 22 ms 3924 KB Output is correct
9 Correct 21 ms 3888 KB Output is correct
10 Correct 19 ms 3876 KB Output is correct
11 Correct 90 ms 16308 KB Output is correct

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 6 ms 328 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 6 ms 340 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -