답안 #875042

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
875042 2023-11-18T14:44:05 Z teo_thrash Vudu (COCI15_vudu) C++14
140 / 140
931 ms 35316 KB
#include <iostream>
#include <cassert>
#include <random>
using namespace std;
 
typedef long long ll;
const int maxn = 1e6+3;
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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8540 KB Output is correct
2 Correct 4 ms 8540 KB Output is correct
3 Correct 4 ms 8540 KB Output is correct
4 Correct 931 ms 34792 KB Output is correct
5 Correct 449 ms 26448 KB Output is correct
6 Correct 726 ms 32712 KB Output is correct
7 Correct 738 ms 33356 KB Output is correct
8 Correct 752 ms 31512 KB Output is correct
9 Correct 894 ms 35316 KB Output is correct
10 Correct 729 ms 32944 KB Output is correct