Submission #971883

#TimeUsernameProblemLanguageResultExecution timeMemory
971883SunbaeVudu (COCI15_vudu)C++17
42 / 140
32 ms5844 KiB
#include <bits/stdc++.h> typedef long long ll; using namespace std; const int N = 1e5 + 5; int m; ll bit[N], qs[N], P; vector<ll> cp; int pos(ll x){return upper_bound(cp.begin(), cp.end(), x) - cp.begin();} void upd(int i){for(; i<=m; i+=i&-i) ++bit[i];} ll qry(int i){ll res = 0; for(; i; i-=i&-i) res += bit[i]; return res;} signed main(){ int n; scanf("%d", &n); for(int i = 1; i<=n; ++i){ scanf("%lld", qs+i); qs[i] += qs[i-1]; } scanf("%lld", &P); for(ll i = 0; i<=n; ++i) cp.push_back(qs[i] - P*i); sort(cp.begin(), cp.end()); cp.resize(unique(cp.begin(), cp.end()) - cp.begin()); m = cp.size(); upd(pos(0)); ll Ans = 0; for(ll i = 1; i<=n; ++i){ Ans += qry(pos(qs[i] - P*i)); upd(pos(qs[i] - P*i)); } printf("%lld", Ans); }

Compilation message (stderr)

vudu.cpp: In function 'int main()':
vudu.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  int n; scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
vudu.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   scanf("%lld", qs+i);
      |   ~~~~~^~~~~~~~~~~~~~
vudu.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |  scanf("%lld", &P);
      |  ~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...