Submission #883460

#	Time	Username	Problem	Language	Result	Execution time	Memory
883460		borisAngelov	Izbori (COCI22_izbori)	C++17	110 / 110	1024 ms	45504 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200005;

int n;

int a[maxn];

vector<int> byPosition[maxn];

void read()
{
    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
}

int b[maxn];
int pref[maxn];

long long divideAndConquer(int l, int r)
{
    if (l > r)
    {
        return 0;
    }

    if (l == r)
    {
        return 1;
    }

    int mid = (l + r) / 2;

    set<int> candidates;
    unordered_map<int, int> cnt;

    for (int i = mid; i >= l; --i)
    {
        ++cnt[a[i]];

        if (cnt[a[i]] > (mid - i) / 2)
        {
            candidates.insert(a[i]);
        }
    }

    cnt.clear();

    for (int i = mid; i <= r; ++i)
    {
        ++cnt[a[i]];

        if (cnt[a[i]] > (i - mid + 1) / 2)
        {
            candidates.insert(a[i]);
        }
    }

    long long ans = 0;

    for (auto currentCandidate : candidates)
    {
        for (int i = l; i <= r; ++i)
        {
            if (a[i] == currentCandidate)
            {
                b[i] = +1;
            }
            else
            {
                b[i] = -1;
            }
        }

        cnt.clear();

        int sum = 0;
        ++cnt[sum];

        for (int i = l; i <= mid - 1; ++i)
        {
            sum += b[i];
            ++cnt[sum];
        }

        int upTo = (r - l + 1);

        for (int i = -upTo; i <= upTo; ++i)
        {
            cnt[i] += cnt[i - 1];
        }

        for (int i = mid; i <= r; ++i)
        {
            sum += b[i];
            ans += cnt[sum - 1];
        }
    }

    return ans + divideAndConquer(l, mid - 1) + divideAndConquer(mid + 1, r);
}

void solve()
{
    cout << divideAndConquer(1, n) << endl;
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    read();
    solve();

    return 0;
}

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