Submission #696678

#	Time	Username	Problem	Language	Result	Execution time	Memory
696678		minhnhatnoe	Izbori (COCI22_izbori)	C++14	110 / 110	1571 ms	4332 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


const int SQRT = 450;
inline void cprs(vector<int> &a){
    vector<int> b = a;
    sort(b.begin(), b.end());
    for (int &x: a)
        x = lower_bound(b.begin(), b.end(), x) - b.begin();
}
vector<int> a, cnt;
vector<int> ccnt;
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n;
    a.resize(n);
    for (int i=0; i<n; i++)
        cin >> a[i];
    cprs(a);
    cnt.resize(n);
    for (int i=0; i<n; i++)
        cnt[a[i]]++;
    ccnt.resize(n);

    ll result = 0;
    // Numbers <= SQRT
    for (int start=0; start<n; start++){
        pair<int, int> pval(-1, -1);
        int max_step = min(SQRT*2, n - start + 1);
        for (int step=1; step < max_step; step++){
            int need = step/2 + 1;
            int val = a[start+step-1];
            ccnt[val]++;
            pval = max(pval, make_pair(ccnt[val], val));
            if (pval.first >= need && cnt[pval.second] <= SQRT)
                result++;
        }
        for (int step=1; step < max_step; step++){
            int val = a[start+step-1];
            ccnt[val]--;
        }
    }
    // Numbers > SQRT
    ccnt.resize(n*2+1);
    ccnt[n] = 1;
    for (int val=0; val<n; val++){
        if (cnt[val] <= SQRT) continue;
        int prefix = 0;
        int pos = n;
        for (int i=0; i<n; i++){
            if (a[i] == val){
                prefix += ccnt[pos];
                pos++;
            }
            else{
                pos--;
                prefix -= ccnt[pos];
            }
            result += prefix;
            ccnt[pos]++;
        }
        pos = n;
        for (int i=0; i<n; i++){
            if (a[i] == val) pos++;
            else pos--;
            ccnt[pos]--;
        }
    }
    cout << result << "\n";
}

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