Submission #1175686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175686		DangKhoizzzz	Izbori (COCI22_izbori)	C++20	25 / 110	5 ms	1092 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 1e5 + 7;

int n , a[maxn];


namespace subtask2
{
    bool check() {return (n <= 2000);}

    int cnt[maxn];

    void compress()
    {
        vector <int> val;
        for(int i = 1; i <= n; i++)
        {
            val.push_back(a[i]);
        }
        sort(val.begin() , val.end());
        val.erase(unique(val.begin() , val.end()) , val.end());
        for(int i = 1; i <= n; i++)
        {
            a[i] = lower_bound(val.begin() , val.end() , a[i]) - val.begin();
        }
    }

    void solve()
    {
        //cout << "yes" << '\n';
        compress();
        int ans = 0;

        for(int i = 1; i <= n; i++)
        {
            int mx = 0;
            for(int i = 0; i < n; i++) cnt[i] = 0;

            for(int j = i; j <= n; j++)
            {
                cnt[a[j]]++;
                mx = max(mx , cnt[a[j]]);
                ans += (mx > (j - i + 1)/2);
            }
        }
        cout << ans << '\n';
    }
}

namespace subtask3
{
    map <int , int> cnt;

    int pref = 0;
    int ans = n*(n+1)/2;

    void solve()
    {
        cnt[pref]++;

        for(int i = 1; i <= n; i++)
        {
            if(a[i] == 1) a[i] = -1;
            else a[i] = 1;
        }

        for(int i = 1; i <= n; i++)
        {
            pref += a[i];
            ans -= cnt[-pref];
            cnt[pref]++;
        }

        cout << ans << '\n';
    }
}

void solve()
{
    cin >> n;
    for(int i =1 ; i <= n; i++) cin >> a[i];
    if(subtask2::check()) subtask2::solve();
    else subtask3::solve();
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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