Submission #380602

#	Time	Username	Problem	Language	Result	Execution time	Memory
380602		Aryan_Raina	Vudu (COCI15_vudu)	C++14	140 / 140	789 ms	40924 KiB

vudu

#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 / 140