oj.uz

Submission #972458

# Submission time Handle Problem Language Result Execution time Memory
972458 2024-04-30T12:50:59 Z blackslex Vudu (COCI15_vudu) C++17
140 / 140
 260 ms 45232 KB 
#include<bits/stdc++.h>
#define lsb(x) (x &(-x))

using namespace std;
using ll = long long;

const int N = 1e6 + 5;
int n, fwk[N];
ll P;

void upd (int idx, int val) {
    for (; idx < N; idx += lsb(idx)) fwk[idx] += val;
}

int qr (int idx) {
    int res = 0;
    for (; idx; idx -= lsb(idx)) res += fwk[idx];
    return res;
}

int main() {
    scanf("%d", &n);
    vector<ll> a(n + 5), pref(n + 5), c, idx(n + 5);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), pref[i] = pref[i - 1] + a[i];
    scanf("%lld", &P);
    for (int i = 0; i <= n; i++) c.emplace_back(pref[i] - P * i);
    sort(c.begin(), c.end());
    c.resize(unique(c.begin(), c.end()) - c.begin());
    for (int i = 0; i <= n; i++) idx[i] = lower_bound(c.begin(), c.end(), pref[i] - P * i) - c.begin(), idx[i]++;
    ll ans = 0; upd(idx[0], 1);
    for (int i = 1; i <= n; i++) ans += qr(idx[i]), upd(idx[i], 1);
    printf("%lld", ans);
}

Compilation message

vudu.cpp: In function 'int main()':
vudu.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
vudu.cpp:24:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), pref[i] = pref[i - 1] + a[i];
      |                                  ~~~~~^~~~~~~~~~~~~~~
vudu.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%lld", &P);
      |     ~~~~~^~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2648 KB Output is correct
2 Correct 3 ms 2648 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 256 ms 43696 KB Output is correct
5 Correct 139 ms 28092 KB Output is correct
6 Correct 219 ms 39848 KB Output is correct
7 Correct 233 ms 40368 KB Output is correct
8 Correct 196 ms 36944 KB Output is correct
9 Correct 260 ms 45232 KB Output is correct
10 Correct 219 ms 40628 KB Output is correct