Submission #1692426

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define NDEBUG
#include "cout11.h"
#endif
#undef NDEBUG
#include <cassert>

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))


vector<ll> _lo, _hi;
vector<int> _cnt;
vector<int> _left, _right;
int _node_last_id = -1;

int node_new(ll lo, ll hi) {
    _lo.pb(lo); _hi.pb(hi); _cnt.pb(0); _left.pb(-1); _right.pb(-1);
    return ++_node_last_id;
}
void node_insert(int node_id, ll val) {
    assert(IN(node_id, 0, _node_last_id));
    ++_cnt[node_id];

    ll lo = _lo[node_id], hi = _hi[node_id];
    if (hi == lo+1) return;

    ll mi = (lo + hi) / 2;
    if (val < mi) {
        if (_left[node_id] == -1) _left[node_id] = node_new(lo, mi);
        node_insert(_left[node_id], val);
    } else {
        if (_right[node_id] == -1) _right[node_id] = node_new(mi, hi);
        node_insert(_right[node_id], val);
    }
}
void node_remove(int node_id, ll val) {
    assert(IN(node_id, 0, _node_last_id));
    --_cnt[node_id];
    ll lo = _lo[node_id], hi = _hi[node_id];
    if (hi == lo+1) return;

    ll mi = (lo + hi) / 2;
    if (val < mi) {
        // assert(left != NULL);
        assert(IN(_left[node_id], 0, _node_last_id));
        node_remove(_left[node_id], val);
    } else {
        assert(IN(_right[node_id], 0, _node_last_id));
        node_remove(_right[node_id], val);
    }
}


class Tree {
public:
    ll minv, maxv, width;
    int bits, cnt;
    int root;

    Tree(ll minv, ll maxv) : minv(minv), maxv(maxv) { // [minv, maxv]
        ll w = maxv - minv + 1;
        for (width=1, bits=0; width < w; width<<=1, ++bits) ;
        // printf("w = %lld, width = %lld, bits = %d\n", w, width, bits);
        root = node_new(0, width);
        cnt = 0;
    }
    ~Tree() {
        // delete root;
    }

    void insert(ll val) {
        node_insert(root, val - minv);
        ++cnt;
    }
    void remove(ll val) {
        node_remove(root, val - minv);
        --cnt;
    }

    int count_till(ll till) { // exclusive, [minv, till)
        ll x = till - minv;

        ll m = 1LL << bits;
        if (x & m) return cnt;

        int node = root;
        int ans = 0;
        for (ll m=1LL<<(bits-1); m>=1; m>>=1) {
            // printf("count_till %lld, m=%lld, p=%d\n", x, m, !!(x & m));
            if (x & m) {
                // >>
                if (_left[node] != -1) ans += _cnt[_left[node]];
                if (_right[node] != -1) node = _right[node]; else break;
            } else {
                // <<
                if (_left[node] != -1) node = _left[node]; else break;
            }
            // if (!node) break;
        }
        return ans;
    }
    int count_from(ll from) { // inclusive, [from, maxv]
        return cnt - count_till(from);
    }

#if 0
    void dump() {
        root->dump();
    }
#endif
};


void solve(int N, int K, vector<int>& a) {
    rep(i, N) a[i] -= K;

    vector<ll> ac(N+1, 0);
    rep(i, N) ac[i+1] = ac[i] + a[i];

    ll minv = *min_element(ALL(ac)), maxv = *max_element(ALL(ac));

    // (-1e9 .. +1e9)x2e5
    Tree *tree = new Tree(minv, maxv);
    rep1(i, N) tree->insert(ac[i]);
    // tree->dump();

    ll total = 0;
    rep1(i, N) {
        ll from = ac[i-1];
        int cnt_from = tree->count_from(from);
        total += cnt_from;
        // printf("%d) %lld, count_from(%lld)=%d\n", i, ac[i], from, cnt_from);
        tree->remove(ac[i]);
    }

    cout << total << endl;
    fflush(stdout);

    delete tree;
}

int main() {
    _lo.clear();
    _hi.clear();
    _cnt.clear();
    _left.clear();
    _right.clear();
    _node_last_id = -1;

    int N, K;
    scanf("%d %d", &N, &K);
    vector<int> a(N);
    rep(i, N) scanf("%d", &a[i]);

    solve(N, K, a);
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:178:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &K);
                           ^
./Main.cpp:180:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     rep(i, N) scanf("%d", &a[i]);
                                 ^

Judge Result