oj.uz

Submission #98774

# Submission time Handle Problem Language Result Execution time Memory
98774 2019-02-25T20:41:30 Z someone_aa Vudu (COCI15_vudu) C++17
42 / 140
 1000 ms 66560 KB 
#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 = 3 * 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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1280 KB Output is correct
2 Correct 9 ms 1024 KB Output is correct
3 Correct 7 ms 896 KB Output is correct
4 Runtime error 666 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Execution timed out 1067 ms 64160 KB Time limit exceeded
6 Runtime error 642 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 651 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 691 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 637 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 653 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)