oj.uz

Submission #380593

# Submission time Handle Problem Language Result Execution time Memory
380593 2021-03-22T12:21:58 Z Aryan_Raina Vudu (COCI15_vudu) C++14
56 / 140
 893 ms 65540 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());
    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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1004 KB Output is correct
2 Correct 6 ms 876 KB Output is correct
3 Correct 6 ms 876 KB Output is correct
4 Runtime error 482 ms 65536 KB Execution killed with signal 9
5 Correct 893 ms 60272 KB Output is correct
6 Runtime error 468 ms 65540 KB Execution killed with signal 9
7 Runtime error 530 ms 65540 KB Execution killed with signal 9
8 Runtime error 434 ms 65540 KB Execution killed with signal 9
9 Runtime error 483 ms 65540 KB Execution killed with signal 9
10 Runtime error 499 ms 65536 KB Execution killed with signal 9