oj.uz

Submission #533541

# Submission time Handle Problem Language Result Execution time Memory
533541 2022-03-06T09:08:34 Z kartel Izbori (COCI22_izbori) C++14
40 / 110
 3000 ms 19032 KB 
#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 = 500;

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);
    }
}

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

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);
            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);
    }

    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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9748 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9748 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 5 ms 9804 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 8 ms 9676 KB Output is correct
10 Correct 5 ms 9676 KB Output is correct
11 Correct 9 ms 9676 KB Output is correct
12 Correct 9 ms 9796 KB Output is correct
13 Correct 8 ms 9788 KB Output is correct
14 Correct 6 ms 9676 KB Output is correct
15 Correct 8 ms 9676 KB Output is correct
16 Correct 8 ms 9676 KB Output is correct
17 Correct 6 ms 9848 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 14280 KB Output is correct
2 Correct 59 ms 15456 KB Output is correct
3 Correct 36 ms 12872 KB Output is correct
4 Correct 61 ms 15432 KB Output is correct
5 Correct 86 ms 15824 KB Output is correct
6 Correct 70 ms 16056 KB Output is correct
7 Correct 66 ms 16072 KB Output is correct
8 Correct 62 ms 16072 KB Output is correct
9 Correct 63 ms 15744 KB Output is correct
10 Correct 66 ms 15820 KB Output is correct
11 Correct 60 ms 15244 KB Output is correct

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9748 KB Output is correct
6 Correct 5 ms 9676 KB Output is correct
7 Correct 5 ms 9804 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 8 ms 9676 KB Output is correct
10 Correct 5 ms 9676 KB Output is correct
11 Correct 9 ms 9676 KB Output is correct
12 Correct 9 ms 9796 KB Output is correct
13 Correct 8 ms 9788 KB Output is correct
14 Correct 6 ms 9676 KB Output is correct
15 Correct 8 ms 9676 KB Output is correct
16 Correct 8 ms 9676 KB Output is correct
17 Correct 6 ms 9848 KB Output is correct
18 Correct 45 ms 14280 KB Output is correct
19 Correct 59 ms 15456 KB Output is correct
20 Correct 36 ms 12872 KB Output is correct
21 Correct 61 ms 15432 KB Output is correct
22 Correct 86 ms 15824 KB Output is correct
23 Correct 70 ms 16056 KB Output is correct
24 Correct 66 ms 16072 KB Output is correct
25 Correct 62 ms 16072 KB Output is correct
26 Correct 63 ms 15744 KB Output is correct
27 Correct 66 ms 15820 KB Output is correct
28 Correct 60 ms 15244 KB Output is correct
29 Correct 80 ms 15348 KB Output is correct
30 Correct 26 ms 12108 KB Output is correct
31 Correct 58 ms 14304 KB Output is correct
32 Correct 129 ms 19032 KB Output is correct
33 Correct 52 ms 14512 KB Output is correct
34 Correct 64 ms 14812 KB Output is correct
35 Correct 39 ms 13188 KB Output is correct
36 Correct 22 ms 11924 KB Output is correct
37 Correct 25 ms 12256 KB Output is correct
38 Correct 212 ms 16736 KB Output is correct
39 Correct 216 ms 16428 KB Output is correct
40 Correct 221 ms 16672 KB Output is correct
41 Correct 207 ms 16416 KB Output is correct
42 Correct 223 ms 16628 KB Output is correct
43 Correct 430 ms 16872 KB Output is correct
44 Correct 469 ms 16976 KB Output is correct
45 Correct 462 ms 16896 KB Output is correct
46 Correct 469 ms 16872 KB Output is correct
47 Correct 517 ms 16960 KB Output is correct
48 Execution timed out 3041 ms 15712 KB Time limit exceeded
49 Halted 0 ms 0 KB -