oj.uz

Submission #875041

# Submission time Handle Problem Language Result Execution time Memory
875041 2023-11-18T14:42:34 Z teo_thrash Vudu (COCI15_vudu) C++14
42 / 140
 20 ms 4640 KB 
#include <iostream>
#include <cassert>
#include <random>
using namespace std;
 
typedef long long ll;
const int maxn = 2e5;
int a[maxn];
 
int root, NODE;
ll val[maxn+1];
int sz[maxn+1];
int prior[maxn+1];
int lft[maxn+1];
int rght[maxn+1];
 
void recalc(int t) {
    sz[t] = sz[lft[t]] + sz[rght[t]] + 1;
}
 
void split(int t, ll x, int &tl, int &tr) {
    if (!t) {
        tl = tr = 0;
        return;
    }
    if (val[t] <= x) {
        split(rght[t], x, tl, tr);
        rght[t] = tl;
        tl = t;
    } else {
        split(lft[t], x, tl, tr);
        lft[t] = tr;
        tr = t;
    }
    recalc(t);
}
 
int mrg(int t1, int t2) {
    if (!t1 || !t2) return t1? t1: t2;
    if (prior[t1] < prior[t2]) swap(t1, t2);
    if (val[t2] <= val[t1]) {
        lft[t1] = mrg(lft[t1], t2);
    } else {
        rght[t1] = mrg(rght[t1], t2);
    }
    recalc(t1);
    assert(t1 >= 0);
    return t1;
}
 
void insrt(ll x) {
    ++NODE;
    sz[NODE] = 1;
    val[NODE] = x;
    prior[NODE] = rand();
    if (!root) {
        root = NODE;
    } else {
        int tl, tr;
        split(root, x, tl, tr);
        root = mrg(mrg(tl, NODE), tr);
    }
}
 
int count_lte(ll x) {
    int tl, tr;
    split(root, x, tl, tr);
    int ans = sz[tl];
    root = mrg(tl, tr);
 
    return ans;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
  	
  	int n, k;
  	cin>>n;
 
    for (int i=0; i<n; ++i) cin>>a[i];
  	cin>>k;
 
    ll prefsum = 0;
    ll ans = 0;
    insrt(0);
    for (int i=0; i<n; ++i) {
        prefsum += a[i]-k;
        ans += count_lte(prefsum);
        insrt(prefsum);
    }
 
    cout << ans << endl;
}

Subtask #1
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4444 KB Output is correct
2 Correct 5 ms 4444 KB Output is correct
3 Correct 4 ms 4640 KB Output is correct
4 Runtime error 19 ms 4264 KB Execution killed with signal 11
5 Runtime error 17 ms 4312 KB Execution killed with signal 11
6 Runtime error 17 ms 4188 KB Execution killed with signal 11
7 Runtime error 20 ms 4124 KB Execution killed with signal 11
8 Runtime error 17 ms 4164 KB Execution killed with signal 11
9 Runtime error 17 ms 4188 KB Execution killed with signal 11
10 Runtime error 18 ms 4316 KB Execution killed with signal 11