Submission #972458

#	Time	Username	Problem	Language	Result	Execution time	Memory
972458		blackslex	Vudu (COCI15_vudu)	C++17	140 / 140	260 ms	45232 KiB

vudu

#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 (stderr)

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 / 140