oj.uz

Submission #533505

# Submission time Handle Problem Language Result Execution time Memory
533505 2022-03-06T08:19:00 Z kartel Izbori (COCI22_izbori) C++14
25 / 110
 3000 ms 12768 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")
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);
    }
}

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) {
            calc_small(x);
        } else {
            calc_big(x);
        }
    }
    cout << ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3094 ms 12768 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9620 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 7 ms 9676 KB Output is correct
5 Correct 7 ms 9676 KB Output is correct
6 Correct 6 ms 9760 KB Output is correct
7 Correct 61 ms 9804 KB Output is correct
8 Correct 5 ms 9676 KB Output is correct
9 Correct 6 ms 9676 KB Output is correct
10 Correct 7 ms 9676 KB Output is correct
11 Correct 6 ms 9676 KB Output is correct
12 Correct 6 ms 9776 KB Output is correct
13 Correct 6 ms 9676 KB Output is correct
14 Correct 6 ms 9676 KB Output is correct
15 Correct 6 ms 9676 KB Output is correct
16 Correct 9 ms 9676 KB Output is correct
17 Correct 15 ms 9676 KB Output is correct
18 Execution timed out 3094 ms 12768 KB Time limit exceeded
19 Halted 0 ms 0 KB -