Submission #250959

#	Time	Username	Problem	Language	Result	Execution time	Memory
250959		kingfran1907	Vudu (COCI15_vudu)	C++14	140 / 140	472 ms	26336 KiB

vudu

#include <bits/stdc++.h>

using namespace std;
typedef long long llint;
const int maxn = 1e6+10;

int n, p;
llint niz[maxn];
vector< llint > v;
int loga[maxn];

void update(int x, int val) {
    for (x++; x < maxn; x += x & -x)
        loga[x] += val;
}

int query(int x) {
    int out = 0;
    for (x++; x > 0; x -= x & -x)
        out += loga[x];
    return out;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", niz+i);
    scanf("%d", &p);

    for (int i = 0; i < n; i++)
        niz[i] -= p;

    v.push_back(0);
    v.push_back(niz[0]);
    for (int i = 1; i < n; i++) {
        niz[i] += niz[i - 1];
        v.push_back(niz[i]);
    }

    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    for (int i = 0; i < n; i++)
        niz[i] = lower_bound(v.begin(), v.end(), niz[i]) - v.begin();

    update(lower_bound(v.begin(), v.end(), 0) - v.begin(), 1);

    llint sol = 0;
    for (int i = 0; i < n; i++) {
        sol += query(niz[i]);
        update(niz[i], 1);
    }
    printf("%lld\n", sol);
    return 0;
}

Compilation message (stderr)

vudu.cpp: In function 'int main()':
vudu.cpp:27:26: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'llint* {aka long long int*}' [-Wformat=]
         scanf("%d", niz+i);
                     ~~~~~^
vudu.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
vudu.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", niz+i);
         ~~~~~^~~~~~~~~~~~~
vudu.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &p);
     ~~~~~^~~~~~~~~~

• Subtask 1: 140 / 140