oj.uz

Submission #533521

# Submission time Handle Problem Language Result Execution time Memory
533521 2022-03-06T08:47:58 Z kartel Izbori (COCI22_izbori) C++14
0 / 110
 3000 ms 12716 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 = 300;

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 ps_l = max(ps2[x][j + 1] - 1 - mx_len + 1, ps1[x][i - 1] + 1);
            ans += max(0ll, (ps1[x][i] - ps_l + 1) * 1ll * min(mx_len, (ps2[x][j + 1] - ps2[x][j]))); /// [ps_l; ps1[i]] = all_segnent
            int len = max(0, min(ps_l - ps1[x][i - 1] - 1, mx_len));
            ans += get_ar(min(mx_len, ps2[x][j + 1] - ps2[x][j] - 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() % 3;
        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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Incorrect 5 ms 9676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Incorrect 5 ms 9676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3055 ms 12716 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 9676 KB Output is correct
3 Incorrect 5 ms 9676 KB Output isn't correct
4 Halted 0 ms 0 KB -