Submission #1269202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269202		khoad	Izbori (COCI22_izbori)	C++20	10 / 110	301 ms	1992 KiB

Main

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

#define endl '\n'
#define inf32 ((int)1e9 + 7)
#define inf64 ((long long)1e18 + 7)
#define MASK32(x) (1 << (x))
#define MASK64(x) (1ll << (x))
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define all(a) begin(a), end(a)
#define isz(a) ((int)a.size())

const int N = 4e5 + 1, S = 670;

int a[N], cnt[N], b[N], cnt1[N];
bool heavy[N];

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

    int n;
    cin >> n;
    vector<int> compress;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        compress.push_back(a[i]);
    }
    sort(all(compress));
    for(int i = 1; i <= n; ++i) {
        a[i] = upper_bound(all(compress), a[i]) - begin(compress);
        ++cnt[a[i]];
    }
    long long res = 0;
    for(int i = 1; i <= n; ++i) {
        if(cnt[i] <= S) continue;
        heavy[i] = 1;
        long long s = 0;
        for(int j = 1, p = 0; j <= n; ++j) {
            if(a[j] == i) {
                s += cnt1[p + n];
                ++cnt1[++p + n];
            }
            else {
                s -= cnt1[p - 1 + n];
                ++cnt1[--p + n];
            }
            res += s;
        }
        for(int j = 1, p = 0; j <= n; ++j) {
            p += (a[j] == i);
            cnt1[p + n] = 0;
        }
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = i, mx = -1; j <= min(i + S * 2 - 1, n); ++j) {
            ++cnt1[a[j]];
            if(mx == -1 || cnt1[mx] < cnt1[a[j]]) mx = a[j];
            if(!heavy[mx] && cnt1[mx] * 2 > j - i + 1) ++res;
        }
        for(int j = i; j <= min(i + S * 2 - 1, n); ++j) cnt1[a[j]] = 0;
    }
    cout << res;

    return 0;
}

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