oj.uz

Submission #1116657

# Submission time Handle Problem Language Result Execution time Memory
1116657 2024-11-22T06:06:30 Z rshohruh Vudu (COCI15_vudu) C++17
140 / 140
 329 ms 37764 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:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int i = 0; i < V.size(); ++i) {
      |                     ~~^~~~~~~~~~
vudu.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
vudu.cpp:41:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     for (int i = 0; i < n; ++i) scanf("%lf", &a[i]);
      |                                 ~~~~~^~~~~~~~~~~~~~
vudu.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d", &p);
      |     ~~~~~^~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4688 KB Output is correct
2 Correct 3 ms 4688 KB Output is correct
3 Correct 3 ms 4688 KB Output is correct
4 Correct 297 ms 36484 KB Output is correct
5 Correct 164 ms 28336 KB Output is correct
6 Correct 259 ms 32984 KB Output is correct
7 Correct 329 ms 33924 KB Output is correct
8 Correct 234 ms 31476 KB Output is correct
9 Correct 311 ms 37764 KB Output is correct
10 Correct 252 ms 33380 KB Output is correct