Submission #968099

# Submission time Handle Problem Language Result Execution time Memory
968099 2024-04-23T07:41:09 Z vjudge1 Vudu (COCI15_vudu) C++17
140 / 140
199 ms 31716 KB
#include <iostream>
#include <algorithm>

using namespace std;
using ll = long long;
using pii = pair<ll, int>;
#define fr first
#define se second
const int N = 1e6+2;

ll n, a[N], fw[N];
pii qs[N];

void upd(int i){
    for (;i < N;i+=i&-i) fw[i]++;
}

ll qry(int i, ll res = 0){
    for (;i;i-=i&-i) res += fw[i]; return res;
}

int main()
{
    ll p, ans = 0; scanf("%lld", &n);
    for (int i = 1;i <= n;i++) scanf("%lld", a+i);
    scanf("%lld", &p);

    for (int i = 1;i <= n;i++) a[i] -= p;
    for (int i = 1;i <= n;i++) qs[i] = {a[i]+qs[i-1].fr, i};
    sort(qs+1, qs+n+1);

    for (int i = 1;i <= n;i++){
        int x = qs[i].se;
        ans += qry(x); upd(x);
        ans += qs[i].fr >= 0;
    }
    printf("%lld", ans);
}

Compilation message

vudu.cpp: In function 'll qry(int, ll)':
vudu.cpp:19:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   19 |     for (;i;i-=i&-i) res += fw[i]; return res;
      |     ^~~
vudu.cpp:19:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   19 |     for (;i;i-=i&-i) res += fw[i]; return res;
      |                                    ^~~~~~
vudu.cpp: In function 'int main()':
vudu.cpp:24:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     ll p, ans = 0; scanf("%lld", &n);
      |                    ~~~~~^~~~~~~~~~~~
vudu.cpp:25:37: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     for (int i = 1;i <= n;i++) scanf("%lld", a+i);
      |                                ~~~~~^~~~~~~~~~~~~
vudu.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%lld", &p);
      |     ~~~~~^~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 199 ms 31400 KB Output is correct
5 Correct 106 ms 23892 KB Output is correct
6 Correct 163 ms 29880 KB Output is correct
7 Correct 180 ms 30548 KB Output is correct
8 Correct 153 ms 27988 KB Output is correct
9 Correct 198 ms 31716 KB Output is correct
10 Correct 168 ms 29776 KB Output is correct