oj.uz

Submission #250959

# Submission time Handle Problem Language Result Execution time Memory
250959 2020-07-19T16:57:45 Z kingfran1907 Vudu (COCI15_vudu) C++14
140 / 140
 472 ms 26336 KB 
#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

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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 444 ms 25872 KB Output is correct
5 Correct 240 ms 18276 KB Output is correct
6 Correct 375 ms 23760 KB Output is correct
7 Correct 383 ms 24272 KB Output is correct
8 Correct 341 ms 21976 KB Output is correct
9 Correct 472 ms 26336 KB Output is correct
10 Correct 380 ms 23760 KB Output is correct