Submission #380593

#	Time	Username	Problem	Language	Result	Execution time	Memory
380593		Aryan_Raina	Vudu (COCI15_vudu)	C++14	56 / 140	893 ms	65540 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());
    map<int, int> mp; int cnt = 0;
    for (int i : tmp) if (!mp.count(i)) mp[i] = cnt++;
    SegTree st; st.init(cnt); 
    st.update(mp[0]);
    int ans = 0; psum = 0;
    for (int i = 0; i < n; i++) {
        psum += a[i];
        int diff = psum - (i+1)*p;
        ans += st.sum(mp[tmp[0]], mp[diff]+1);
        st.update(mp[diff]);
    }
    cout<<ans<<"\n";
}

• Subtask 1: 56 / 140