답안 #75444

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
75444 2018-09-09T19:46:37 Z WLZ Vudu (COCI15_vudu) C++17
42 / 140
367 ms 31536 KB
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

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

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

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

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector< pair<int, int> > a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i].first;
    a[i].second = i;
  }
  int p;
  cin >> p;
  for (int i = 0; i < n; i++) {
    a[i].first -= p;
  }
  for (int i = 1; i < n; i++) {
    a[i].first += a[i - 1].first;
  }
  sort(a.begin(), a.end());
  vector<int> rep(n);
  rep[a[0].second] = 0;
  for (int i = 1; i < n; i++) {
    rep[a[i].second] = rep[a[i - 1].second];
    if (a[i].first > a[i - 1].first) {
      rep[a[i].second]++;
    }
  }
  fenwick<int> fenw(n + 1);
  long long ans = 0ll;
  for (int i = 0; i < n; i++) {
    if (a[i].first >= 0) {
      ans++;
    }
    ans += (long long) fenw.get(rep[i]);
    fenw.modify(rep[i], +1);
  }
  cout << ans << endl;
  return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 668 KB Output is correct
3 Correct 3 ms 712 KB Output is correct
4 Incorrect 367 ms 25100 KB Output isn't correct
5 Incorrect 178 ms 25100 KB Output isn't correct
6 Incorrect 285 ms 29288 KB Output isn't correct
7 Incorrect 298 ms 29820 KB Output isn't correct
8 Incorrect 248 ms 29820 KB Output isn't correct
9 Incorrect 345 ms 31536 KB Output isn't correct
10 Incorrect 302 ms 31536 KB Output isn't correct