Submission #98773

#	Time	Username	Problem	Language	Result	Execution time	Memory
98773		someone_aa	Vudu (COCI15_vudu)	C++17	42 / 140	1076 ms	66560 KiB

vudu

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define P pair<ll, ll>
using namespace std;
const int maxn = 1000100;
const int maxm = 2 * maxn;
int tree[4*maxm], m;
void update(int x, int li=1, int ri=m, int index=1) {
    if(li == ri) {
        tree[index]++;
    }
    else {
        int mid = (li + ri) / 2;
        if(x <= mid) update(x, li, mid, 2*index);
        else update(x, mid+1, ri, 2*index+1);
        tree[index] = tree[2*index] + tree[2*index+1];
    }
}

int query(int ql, int qr, int li=1, int ri=m, int index=1) {
    if(li > qr || ri < ql) return 0;
    else if(li >= ql && ri <= qr) return tree[index];
    else {
        int mid = (li + ri) / 2;
        return query(ql,qr,li,mid,2*index) + query(ql,qr,mid+1,ri,2*index+1);
    }
}

ll n, d, arr[maxn];
map<ll, ll> ind;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>arr[i];
    }
    cin>>d;

    vector<ll>values;
    ll sum = 0LL;
    for(ll i=1LL;i<=n;i++) {
        values.pb(sum - d*i);
        sum += arr[i];
        values.pb(sum - d*i - d);
    }

    sort(values.begin(), values.end());

    int br = 1;
    for(ll i:values) {
        ind[i] = br++;
    }
    m = br;
    sum = 0LL;
    ll result = 0LL;
    for(int i=1;i<=n;i++) {
        update(ind[sum - d*i]);
        //cout<<i<<": "<<sum-d*i<<", "<<ind[sum-d*i]<<" -> ";
        sum += arr[i];
        result += 1LL * query(1, ind[sum - d*i - d]);
        //cout<<sum - d*i - d<<", "<<ind[sum-d*i-d]<<"\n";
    }
    cout<<result<<"\n";
    return 0;
}

• Subtask 1: 42 / 140