Submission #1688781

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
using namespace std;
typedef long long ll;

template<typename T>
struct BIT {
  vector<T> data;
  BIT() {}
  BIT(int n) : data(n+1, 0) {}
  void init(int n) { data.assign(n+1, 0); }
  T sum(int ed) const {
    // cerr << ">> " << ed << endl;
    for(T res(0); ; ed &= ed-1) if(ed) res += data[ed]; else return res;
  }
  void add(int i, const T& x) {
    // cerr << ">>> " << i << endl;
    for(++i; i < (int)data.size(); i += i&-i) data[i] += x;
  }
};

int n;
ll k;
ll vs[200000+10];
ll ss[200000+10];
ll ts[200000+10];

int main(void) {
  scanf("%d%lld", &n, &k);
  REP(i, n) {
    scanf("%lld", &vs[i]);
    ts[i+1] = ss[i+1] = ss[i] + vs[i] - k;
  }

  sort(ts, ts + n+1);
  ll res = 0;
  BIT<ll> bit(n+1);
  {
    int idx = lower_bound(ts, ts+n+1, ss[n]) - ts;
    // cerr << " add to " << idx << endl;
    bit.add(idx, 1);
  }
  for(int i = n-1; i >= 0; --i) {
    // cerr << "i=" << i << ", ss[i]=" << ss[i] << endl; 
    int idx = lower_bound(ts, ts+n+1, ss[i]) - ts;
    // cerr << " + " << bit.sum(n) - bit.sum(idx) << " @ i=" << i << ", idx=" << idx << endl;
    res += bit.sum(n) - bit.sum(idx);
    int idx2 = lower_bound(ts, ts+n+1, ss[i]) - ts;
    // cerr << " add to " << idx2 << endl;
    bit.add(idx2, 1);
  }
  printf("%lld\n", res);
  
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:35:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%lld", &n, &k);
                          ^
./Main.cpp:37:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &vs[i]);
                          ^

Judge Result