Submission #1175834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175834		DangKhoizzzz	Izbori (COCI22_izbori)	C++20	110 / 110	1222 ms	10204 KiB

Main

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

using namespace std;

const int maxn = 2e5 + 7;
const int block = 1000;

struct Fenwick_Tree
{
    int bit[maxn*2];

    void reset()
    {
        for(int i = 0; i < maxn*2; i++) bit[i] = 0;
    }

    void update(int pos , int val)
    {
        while(pos < maxn*2)
        {
            bit[pos] += val;
            pos += (pos & (-pos));
        }
    }

    int get(int pos)
    {
        int sum = 0;
        while(pos > 0)
        {
            sum += bit[pos];
            pos -= (pos & (-pos));
        }
        return sum;
    }
};

int n, a[maxn];
vector <int> pos[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] = upper_bound(val.begin(), val.end(), a[i]) - val.begin();
    }
}

ll ans = 0ll;
Fenwick_Tree cnt;

int mark[maxn];
int occ[maxn];


void solve() // subtask full
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    compress();

    for(int i = 1; i <= n; i++)
    {
        pos[a[i]].push_back(i);
    }

    for(int i = 1; i <= n; i++)
    {
        if((int)pos[i].size() >= block) // heavy
        {
            cnt.reset();
            cnt.update(0 + maxn , 1);
            for(int i = 1; i <= n; i++) mark[i] = -1;
            for(int x: pos[i]) mark[x] = 1;

            int pref = 0;

            for(int i = 1; i <= n; i++)
            {
                pref += mark[i];
                cnt.update(pref + maxn , 1);
                ans += cnt.get(pref + maxn - 1);
            }
        }
    }

    for(int i = 1; i <= maxn; i++)
    {
        for(int j = i; j <= min(i+block*2 , n); j++) occ[a[j]] = 0;

        int mx = 0;

        for(int j = i; j <= min(i+block*2 , n); j++)
        {
            occ[a[j]]++;

            if(pos[a[j]].size() < block) // light
            {
                mx = max(mx , occ[a[j]]);
            }
            if(mx > (j - i + 1)/2) ans++;
        }
    }

    cout << ans << '\n';

    /*
    if(subtask2::check()) subtask2::solve();
    else if(subtask3::check()) subtask3::solve();
    else subtaskfull::solve();
    */


}

int 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: 15 / 15
• Subtask 4: 70 / 70