Submission #75391

# Submission time Handle Problem Language Result Execution time Memory
75391 2018-09-09T13:54:04 Z WLZ Vudu (COCI15_vudu) C++17
42 / 140
1000 ms 66560 KB
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

template<typename T>
class fenwick {
  private: 
    vector<int> fenw;
    int n;
  public:

    fenwick(int _n) : n(_n) {
      fenw.resize(n);
    }

    T get(int x) {
      T v{};
      while (x >= 0) {
        v += fenw[x];
        x = (x & (x + 1)) - 1;
      }
      return v;
    }

    void modify(int x, T v) {
      while (x < n) {
        fenw[x] += v;
        x |= (x + 1);
      }
    }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  int p;
  cin >> p;
  for (int i = 0; i < n; i++) {
    a[i] -= p;
  }
  vector<int> pre = {a[0]};
  for (int i = 1; i < n; i++) {
    pre.push_back(pre.back() + a[i]);
  }
  vector<int> b = pre;
  sort(b.begin(), b.end());
  map<int, int> mp;
  fenwick<int> fenw(n + 1);
  for (int i = 0; i < n; i++) {
    mp[pre[i]] = lower_bound(b.begin(), b.end(), pre[i]) - b.begin();
  }
  long long ans = 0ll;
  for (int i = 0; i < n; i++) {
    if (pre[i] >= 0) {
      ans++;
    }
    ans += fenw.get(mp[pre[i]]);
    fenw.modify(mp[pre[i]], +1);
  }
  cout << ans << endl;
  return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 8 ms 892 KB Output is correct
2 Correct 6 ms 908 KB Output is correct
3 Correct 6 ms 908 KB Output is correct
4 Execution timed out 1079 ms 55440 KB Time limit exceeded
5 Execution timed out 1071 ms 55440 KB Time limit exceeded
6 Execution timed out 1065 ms 66560 KB Time limit exceeded
7 Execution timed out 1075 ms 66560 KB Time limit exceeded
8 Execution timed out 1066 ms 66560 KB Time limit exceeded
9 Execution timed out 1069 ms 66560 KB Time limit exceeded
10 Execution timed out 1082 ms 66560 KB Time limit exceeded