제출 #533499

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533499		kartel	Izbori (COCI22_izbori)	C++14	40 / 110	3074 ms	17296 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()
using namespace std;
typedef long long ll;

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

int t[N];
vector <int> vl, vals;
int pf[N], a[N], 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++) {
        upd(lower_bound(all(vl), 2 * pf[i - 1] - i + 1) - vl.begin(), 1);
        ans += get(lower_bound(all(vl), 2 * pf[i] - i) - vl.begin() - 1);
    }
    for (int i = 1; i <= n; i++) {
        upd(lower_bound(all(vl), 2 * pf[i - 1] - i + 1) - vl.begin(), -1);
    }
}

void calc_small(int x) {
    for (int i = 1; i < sz(ps1[x]); i++) {
        for (int j = i - 1; j < sz(ps2[x]) - 1; j++) {
            int cnt = (j + 1) - i + 1;
            int mx_len = min(ps2[x][j + 1] - ps1[x][i - 1] - 1, 2 * cnt - 1);
            for (int len = ps2[x][j] - ps1[x][i] + 1; len <= mx_len; len++) {
                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;
            }
        }
    }
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        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);
    }

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

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