Submission #4833327


Source Code Expand

Copy
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
using namespace std;

template<typename T>
struct BIT{//1-indexed
private:
  vector<T> data;
  const int n;
public:
  BIT(int sz) : data(sz+1,0), n(sz) {}
  BIT(vector<T> t) : data(t), n((int)t.size()) {}
  T sum(int i){
    T s = 0;
    while(i > 0){
      s += data[i];
      i -= i&(-i);
    }
    return s;
  }

  T sum(int i, size_t j){ return sum(j) - sum(i-1); }//sum[i,j)

  void add(int i, T x){
    while(i <= n){
      data[i] += x;
      i += i&(-i);
    }
  }
};

int main(){
  long long N, K;
  cin >> N >> K;
  vector<long long> A(N);
  map<long long,int> M;
  for(int i = 0; i < N; ++i){
    cin >> A[i];
    A[i] -= K;
    if(i > 0) A[i] += A[i-1];
    ++M[A[i]];
  }
  ++M[0];
  int t = 0;
  for(auto &e : M) e.second = t++;
  BIT<long long> bit(t);
  long long ans = 0;
  bit.add(M[0]+1,1);
  for(int i = 0; i < N; ++i){
    ans += bit.sum(M[A[i]]+1);
    bit.add(M[A[i]]+1,1);
  }
  cout << ans << endl;
  return 0;
}

Submission Info

Submission Time
Task E - Meaningful Mean
User TAB
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1069 Byte
Status
Exec Time 253 ms
Memory 15872 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 a01, a02, a03
All 600 / 600 a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23
Case Name Status Exec Time Memory
a01 1 ms 256 KB
a02 1 ms 256 KB
a03 1 ms 256 KB
b04 1 ms 256 KB
b05 88 ms 1792 KB
b06 253 ms 15872 KB
b07 192 ms 8832 KB
b08 193 ms 8832 KB
b09 237 ms 15872 KB
b10 190 ms 15872 KB
b11 1 ms 256 KB
b12 2 ms 256 KB
b13 58 ms 5888 KB
b14 181 ms 15872 KB
b15 158 ms 8832 KB
b16 144 ms 15872 KB
b17 177 ms 15872 KB
b18 175 ms 15872 KB
b19 147 ms 15872 KB
b20 95 ms 1792 KB
b21 99 ms 1792 KB
b22 154 ms 15872 KB
b23 151 ms 15872 KB