Submission #545707

#	Time	Username	Problem	Language	Result	Execution time	Memory
545707		mat50013	Izbori (COCI22_izbori)	C++11	110 / 110	243 ms	16148 KiB

Main

#include <bits/stdc++.h>

using namespace std;

/// numar elem maj pe [st, dr], atunci e sigur macar in [st, mij], sau [mij + 1, dr]
const int NMAX(200005), ADD(200005);
using ll = long long;
map<int, int> mp;
int cnt, v[NMAX], viz[NMAX], fr[NMAX], nrSum[2 * NMAX];
ll rez;

inline void solve(int st, int dr){
    if(st > dr)
        return;
    if(st == dr){
        ++rez;
        return;
    }
    int mij = (st + dr) / 2;
    solve(st, mij - 1), solve(mij + 1, dr);

    for(int i = st; i <= dr; ++i)
        viz[v[i]] = 0, fr[v[i]] = 0;

    vector<int> haveCh;
    for(int i = mij; i >= st; --i){
        ++fr[v[i]];
        if(fr[v[i]] > (mij - i + 1) / 2 && !viz[v[i]]){
            viz[v[i]] = 1;
            haveCh.push_back(v[i]);
        }
    }
    for(int i = st; i <= dr; ++i)
        fr[v[i]] = 0;
    for(int i = mij + 1; i <= dr; ++i){
        ++fr[v[i]];
        if(fr[v[i]] > (i - mij) / 2 && !viz[v[i]]){
            viz[v[i]] = 1;
            haveCh.push_back(v[i]);
        }
    }

    int lg = dr - st + 1;
    for(auto it: haveCh){
        for(int i = ADD - lg - 1; i <= ADD + lg + 1; ++i)
            nrSum[i] = 0;
        int sum = 0;
        nrSum[0 + ADD] = 1;
        for(int i = st; i < mij; ++i){
            if(v[i] == it)
                sum ++;
            else sum--;
            nrSum[sum + ADD]++;
        }
        for(int i = ADD - lg; i <= ADD + lg; ++i)
            nrSum[i] += nrSum[i - 1];
        for(int i = mij; i <= dr; ++i){
            if(v[i] == it)
                sum++;
            else sum--;
            rez += nrSum[sum + ADD - 1];
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n;
    cin >> n;

    set<int> s;
    for(int i = 1; i <= n; ++i){
        cin >> v[i];
        s.insert(v[i]);
    }

    for(auto it: s)
        mp[it] = ++cnt;

    for(int i = 1; i <= n; ++i)
        v[i] = mp[v[i]];

    solve(1, n);

    cout << rez << '\n';
    return 0;
}

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