Submission #319064

#	Time	Username	Problem	Language	Result	Execution time	Memory
319064		Fischer	Vudu (COCI15_vudu)	C++14	140 / 140	314 ms	15960 KiB

vudu

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 10;
using ll = long long;
ll a[maxn];
int n, p;
int ft[maxn];

void upd(int pos, int v) {
    while (pos < maxn) {
        ft[pos] += v;
        pos += pos&-pos;
    }
}

int qry(int pos) {
    int ans = 0;
    while (pos > 0) {
        ans += ft[pos];
        pos -= pos&-pos;
    }
    return ans;
}

int main() {
    scanf("%d", &n);
    vector<int> id(n + 1);
    iota(id.begin(), id.end(), 0);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld\n", a+i);
        a[i] += a[i-1];
    }
    scanf("%d", &p);
    stable_sort(id.begin(), id.end(), [](int i, int j) {
        return a[i] - i *1ll* p < a[j] - j *1ll* p;
    });
    long long ans = 0;
    for (int i : id) {
        ans += qry(i);
        upd(i + 1, 1);
    }
    printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

vudu.cpp: In function 'int main()':
vudu.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
vudu.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |         scanf("%lld\n", a+i);
      |         ~~~~~^~~~~~~~~~~~~~~
vudu.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |     scanf("%d", &p);
      |     ~~~~~^~~~~~~~~~

• Subtask 1: 140 / 140