Submission #536632

#	Time	Username	Problem	Language	Result	Execution time	Memory
536632		Farhan_HY	Izbori (COCI22_izbori)	C++14	25 / 110	90 ms	16308 KiB

Main

#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 (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 0 / 15
• Subtask 3: 15 / 15
• Subtask 4: 0 / 70