oj.uz

Submission #883459

# Submission time Handle Problem Language Result Execution time Memory
883459 2023-12-05T09:58:01 Z borisAngelov Izbori (COCI22_izbori) C++17
0 / 110
 559 ms 28864 KB 
#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 + 1) / 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Incorrect 2 ms 6488 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Incorrect 2 ms 6488 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 559 ms 28864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Incorrect 2 ms 6488 KB Output isn't correct
4 Halted 0 ms 0 KB -