oj.uz

Submission #23200

# Submission time Handle Problem Language Result Execution time Memory
23200 2017-05-04T12:06:52 Z model_code Vudu (COCI15_vudu) C++11
140 / 140
 453 ms 38124 KB 
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 1 << 20;
typedef pair <double, int> pdi;

int n;
double a[MAXN];

bool cmp (const pdi &A, const pdi &B) {
  if (A.first != B.first) return A.first < B.first;
  return A.second < B.second;
}

int loga[MAXN];
void update (int pos) {
  pos += 10;
  while (pos < MAXN) {
    ++loga[pos];
    pos += pos&-pos;
  }
}

int query (int pos) {
  pos += 10;
  int ret = 0;
  while (pos > 0) {
    ret += loga[pos];
    pos -= pos&-pos;
  }
  return ret;
}

int main (void){
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%lf", &a[i]);
  int p;
  scanf("%d", &p);

  for (int i = 0; i < n; ++i) {
    a[i] -= p;
    if (i > 0) a[i] += a[i-1];
  }

  vector <pdi> V;
  for (int i = 0; i < n; ++i)
    V.push_back(pdi(a[i], i));
  V.push_back(pdi(0, -1));

  sort(V.begin(), V.end(), cmp);
  int pos = 0;
  long long ans = 0;
  for (int i = 0; i < V.size(); ++i) {
    while (pos < i && (V[i].first - V[pos].first) >= 0) update(V[pos++].second);
    ans += query(V[i].second);
  }

  printf("%lld\n", ans);


  return 0;
}

Compilation message

vudu.cpp: In function 'int main()':
vudu.cpp:58:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < V.size(); ++i) {
                     ^
vudu.cpp:40:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
vudu.cpp:41:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 0; i < n; ++i) scanf("%lf", &a[i]);
                                                  ^
vudu.cpp:43:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &p);
                  ^

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13736 KB Output is correct
2 Correct 0 ms 13736 KB Output is correct
3 Correct 0 ms 13736 KB Output is correct
4 Correct 386 ms 38124 KB Output is correct
5 Correct 239 ms 38124 KB Output is correct
6 Correct 359 ms 38124 KB Output is correct
7 Correct 453 ms 38124 KB Output is correct
8 Correct 309 ms 38124 KB Output is correct
9 Correct 403 ms 38124 KB Output is correct
10 Correct 353 ms 38124 KB Output is correct