Submission #1233959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233959		quannnguyen20091	Izbori (COCI22_izbori)	C++20	110 / 110	1504 ms	6864 KiB

Main

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 4e5+5, mod = 1e9+7, inf = 1e18, bl = 400;

int n;
int a[N];
int cnt[N];
int tmp[N];

int bit[N];

int get(int p) {
    int idx = p, ans = 0;
    while (idx>0) {
        ans += bit[idx];
        idx -= (idx&(-idx));
    }
    return ans;
}

void upd(int u, int v) {
    int idx = u;
    while (idx<N) {
        bit[idx]+=v;
        idx+=(idx&(-idx));
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    vector<int> v;
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        v.pb(a[i]);
    }
    sort(all(v)); v.erase(unique(all(v)), v.end());
    for (int i=1; i<=n; i++) {
        a[i] = lower_bound(all(v), a[i])-v.begin()+1;
        cnt[a[i]]++;
    }
    int ans = 0;
    for (int i=1; i<=n; i++) {
        int mx = 0, idx = 0;
        for (int j=i; j<=min(i+2*bl-1, n); j++) {
            tmp[a[j]]++;
            if (tmp[a[j]]>mx) {
                mx = tmp[a[j]];
                idx = a[j];
            }
            if (mx*2>j-i+1 && cnt[idx]<=bl) ans++;
        }
        for (int j=i; j<=min(i+2*bl-1, n); j++) tmp[a[j]]--;
    }
    for (int num=1; num<=n; num++) {
        if (cnt[num]<=bl) continue;
        int dif = 0;
        upd(dif+n+1, 1);
        for (int i=1; i<=n; i++) {
            if (a[i]==num) dif++;
            else dif--;
            ans += get(dif+n+1-1);
            upd(dif+n+1, 1);
        }
        for (int i=0; i<N; i++) bit[i] = 0;
    }
    cout << ans;
}

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