oj.uz

Submission #319064

# Submission time Handle Problem Language Result Execution time Memory
319064 2020-11-03T20:29:38 Z Fischer Vudu (COCI15_vudu) C++14
140 / 140
 314 ms 15960 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 314 ms 15644 KB Output is correct
5 Correct 167 ms 8880 KB Output is correct
6 Correct 261 ms 13716 KB Output is correct
7 Correct 289 ms 14352 KB Output is correct
8 Correct 236 ms 12464 KB Output is correct
9 Correct 314 ms 15960 KB Output is correct
10 Correct 264 ms 13884 KB Output is correct