Submission #533551

#	Time	Username	Problem	Language	Result	Execution time	Memory
533551		kartel	Izbori (COCI22_izbori)	C++14	110 / 110	357 ms	19096 KiB

Main

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define pb push_back
#define sz(x) (int)x.size()
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#define el "\n"
using namespace std;
typedef long long ll;

const int N = 2e5 + 500;
const int SQ = 800;

int t[N];
vector <int> vl, vals;
int pf[N], a[N], n, b[N];
vector <int> ps1[N], ps2[N];
ll ans = 0;

void upd(int v, int val) {for (; v < N; v = (v | (v + 1))) t[v] += val;}
int get(int v) {int ret = 0; for (; v >= 0; v = (v & (v + 1)) - 1) ret += t[v]; return ret;}

void calc_big(int x) {
    vl.clear();
    for (int i = 1; i <= n; i++) {
        pf[i] = pf[i - 1] + (x == a[i]);
        vl.pb(2 * pf[i - 1] - i + 1);
    }
    sort(all(vl));
    vl.resize(unique(all(vl)) - vl.begin());

    for (int i = 1; i <= n; i++) {
        b[i] = lower_bound(all(vl), 2 * pf[i - 1] - i + 1) - vl.begin();
        upd(b[i], 1);
        ans += get(lower_bound(all(vl), 2 * pf[i] - i) - vl.begin() - 1);
    }
    for (int i = 0; i <= n; i++) {
        t[i] = 0;
    }
}

ll get_ar(ll a0, ll cnt, ll d) {
    return ((2 * a0 + d * (cnt - 1)) * cnt) / 2ll;
}

void calc_small(int x) {
    int n = sz(ps1[x]), m = sz(ps2[x]);
    for (int i = 1; i < n; i++) {
        for (int j = i - 1; j < m - 1; j++) {
            int cnt = (j + 1) - i + 1;
            int mx_len = min(ps2[x][j + 1] - ps1[x][i - 1] - 1, 2 * cnt - 1);
            int mn_len = ps2[x][j] - ps1[x][i] + 1;
            if (mn_len > mx_len) {
                continue;
            }

            int R = min(ps2[x][j + 1] - 1, ps1[x][i] + mx_len - 1);
            int seg = R - ps2[x][j] + 1;
            int ps_l = max(R - mx_len + 1, ps1[x][i - 1] + 1);
            ans += max(0ll, (ps1[x][i] - ps_l + 1) * 1ll * seg); /// [ps_l; ps1[i]] = all_segnent
            int len = max(0, min((ps_l - 1 - max(ps2[x][j] - mx_len + 1, ps1[x][i - 1] + 1) + 1),
                                 seg - 1));
            ans += get_ar(seg - 1, len, -1);

//            for (int len = ps2[x][j] - ps1[x][i] + 1; len <= mx_len; len++) {
//                cerr << x << " " << i << " " << j << " " << len << " " << max(0, min(ps1[x][i], min(ps1[x][i] + len - 1, ps2[x][j + 1] - 1) - len + 1) - max(ps2[x][j] - len + 1, ps1[x][i - 1] + 1)) + 1 << el;
//                ans += max(0, min(ps1[x][i], min(ps1[x][i] + len - 1, ps2[x][j + 1] - 1) - len + 1) - max(ps2[x][j] - len + 1, ps1[x][i - 1] + 1)) + 1;
//            }
//            cerr << el;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    mt19937 rnd(time(0));
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
//        a[i] = rnd() % 2;
        vals.pb(a[i]);
    }

    sort(all(vals));
    vals.resize(unique(all(vals)) - vals.begin());

    for (int i = 1; i <= n; i++){
        a[i] = lower_bound(all(vals), a[i]) - vals.begin();
        ps1[a[i]].pb(i);
        ps2[a[i]].pb(i);
    }

    ll sum = 0;
    for (int x = 0; x < min(SQ, sz(vals)); x++) {
        sum += (sz(ps1[x]) + 1) * 1ll * (sz(ps1[x]) + 1);
    }

    for (int x = SQ; x < sz(vals); x++) {
        sum += 2ll * n * 17;
    }
    if (sum < (ll)5e8) {
        for (int x = 0; x < sz(vals); x++) {
            ps1[x].pb(0);
            ps2[x].pb(n + 1);
            sort(all(ps1[x]));
            if (x < SQ) {
                calc_small(x);
            } else {
                calc_big(x);
            }
        }
    } else {
        for (int x = 0; x < sz(vals); x++) {
            if (sz(ps1[x]) < SQ) {
                ps1[x].pb(0);
                ps2[x].pb(n + 1);
                sort(all(ps1[x]));
                calc_small(x);
            } else {
                calc_big(x);
            }
        }
    }
    cout << ans;
}

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