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

vudu

#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);
      |     ~~~~~^~~~~~~~~~~~

Subtask #1

140.0 / 140.0

#	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