oj.uz

Submission #380602

# Submission time Handle Problem Language Result Execution time Memory
380602 2021-03-22T12:38:37 Z Aryan_Raina Vudu (COCI15_vudu) C++14
140 / 140
 789 ms 40924 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define ar array


const int INF = 1e17;
const int MOD = 1e9;

struct SegTree {
    int size;
    vector<int> values;
    void init(int n) {
        size = 1;
        while (size < n) size <<= 1;
        values.resize(2*size);
    }   
    int sum(int l, int r, int x, int lx, int rx) {
        if (lx >= r || l >= rx) return 0;
        if (l <= lx && rx <= r) return values[x];
        int m = (lx + rx) >> 1;
        int s1 = sum(l, r, 2*x+1, lx, m);
        int s2 = sum(l, r, 2*x+2, m, rx);
        return s1+s2;
    }
    int sum(int l, int r) {
        return sum(l, r, 0, 0, size);
    }
    void update(int i, int x, int lx, int rx) {
        if (rx - lx == 1) return void(values[x]++);
        int m = (lx + rx) >> 1;
        if (i < m) update(i, 2*x+1, lx, m);
        else update(i, 2*x+2, m, rx);
        values[x] = values[2*x+1] + values[2*x+2];
    }
    void update(int i) {
        update(i, 0, 0, size);
    }
};

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n; cin>>n;
    vector<int> a(n), tmp(n+1);
    for (int &i : a) cin>>i;
    int p; cin>>p;
    int psum = 0;
    for (int i = 0; i < n; i++) psum += a[i], tmp[i] = psum - (i+1)*p;
    tmp[n] = 0;
    sort(tmp.begin(), tmp.end());
    vector<int> mp = {tmp[0]}; int cnt = 1;
    for (int i = 1; i < n; i++) {
        if (tmp[i-1] == tmp[i]) continue;
        mp.push_back(tmp[i]); ++cnt;
    }
    SegTree st; st.init(cnt);
    st.update(lower_bound(mp.begin(), mp.end(), 0) - mp.begin());
    int ans = 0; psum = 0;
    for (int i = 0; i < n; i++) {
        psum += a[i];
        int diff = psum - (i+1)*p;
        int r = lower_bound(mp.begin(), mp.end(), diff) - mp.begin();
        ans += st.sum(0, r+1);
        st.update(r);
    }
    cout<<ans<<"\n";
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 748 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 3 ms 620 KB Output is correct
4 Correct 789 ms 40272 KB Output is correct
5 Correct 404 ms 29916 KB Output is correct
6 Correct 645 ms 37624 KB Output is correct
7 Correct 700 ms 38480 KB Output is correct
8 Correct 590 ms 35676 KB Output is correct
9 Correct 763 ms 40924 KB Output is correct
10 Correct 657 ms 37968 KB Output is correct