Submission #534589

#	Time	Username	Problem	Language	Result	Execution time	Memory
534589		N1NT3NDO	Izbori (COCI22_izbori)	C++14	110 / 110	2831 ms	5560 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = (int)2e5 + 50;
const int MX = 450;
int n, a[N], cnt[N], f[2 * N], mk[N], skok[N];
vector<int> vec;
bool was[N];
ll ans;

void upd(int x)
{
    for(int i = x; i < 2 * N; i = i | (i + 1)) f[i]++;
}

int get(int x)
{
    int res = 0;

    for(int i = x; i >= 0; i = (i & (i + 1)) - 1)
      res += f[i];
    return res;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("input.txt", "r", stdin);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        vec.pb(a[i]);
    }

    sort(all(vec));

    vec.resize(unique(all(vec)) - vec.begin());

    int m = sz(vec);

    for(int i = 1; i <= n; i++)
    {
        a[i] = lower_bound(all(vec), a[i]) - vec.begin();
        cnt[a[i]]++;
    }

    for(int i = 0; i < m; i++)
    {

        if (cnt[i] < MX) continue;

        for(int j = 0; j < 2 * N; j++) f[j] = 0;

        was[i] = 1;

        upd(N);

        int pr = 0;

        for(int j = 1; j <= n; j++)
        {
            if (a[j] == i) pr++;
            else pr--;
            ans += (ll)get(N + pr - 1);
            upd(N + pr);
        }
    }



    int id = 1;
    for(int i = 1; i <= n; i++)
    {
        int mx = 0, who = -1;

        for(int j = i; j <= min(n, i + MX + MX); j++)
        {
            if (mk[a[j]] != id)
            {
                mk[a[j]] = id;
                skok[a[j]] = 0;
            }

            skok[a[j]]++;

            if (skok[a[j]] > mx)
            {
                mx = skok[a[j]];
                who = a[j];
            }

            if (!was[who] && mx > (j - i + 1) / 2)
              ans++;
        }

        id++;
    }



    cout << ans;
}

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