Submission #516445

#TimeUsernameProblemLanguageResultExecution timeMemory
516445JomnoiMountains (NOI20_mountains)C++17
6 / 100
318 ms36844 KiB
#include <bits/stdc++.h> #define DEBUG 0 using namespace std; const int MX = 3e5 + 10; long long h[MX]; class Fenwick { protected : int N; vector <int> fenwick; public : Fenwick(const int &n) : N(n) { fenwick.resize(N, 0); } int lsb(const int &x) const { return x & -x; } void update(const int &i, const int &val) { for(int idx = i; idx <= N; idx += lsb(idx)) { fenwick[idx] += val; } } int query(const int &i) const { int res = 0; for(int idx = i; idx > 0; idx -= lsb(idx)) { res += fenwick[i]; } return res; } }; int main() { int n; scanf(" %d", &n); set <long long> s; unordered_map <long long, int> mp; for(int i = 1; i <= n; i++) { scanf(" %lld", &h[i]); s.insert(h[i]); } int cnt = 0; for(auto v : s) { mp[v] = ++cnt; } Fenwick fw1(cnt), fw2(cnt); for(int i = 2; i <= n; i++) { fw2.update(mp[h[i]], 1); } fw1.update(mp[h[1]], 1); long long ans = 0; for(int i = 2; i < n; i++) { fw2.update(mp[h[i]], -1); ans += 1ll * fw1.query(mp[h[i]] - 1) * fw2.query(mp[h[i]] - 1); fw1.update(mp[h[i]], 1); } cout << ans; return 0; }

Compilation message (stderr)

Mountains.cpp: In function 'int main()':
Mountains.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf(" %d", &n);
      |     ~~~~~^~~~~~~~~~~
Mountains.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf(" %lld", &h[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...