Submission #499376

#TimeUsernameProblemLanguageResultExecution timeMemory
499376sumit_kk10Mountains (NOI20_mountains)C++17
100 / 100
123 ms32584 KiB
#include <bits/stdc++.h> #define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL) using namespace std; const int N = 1e6 + 5; int n, fenwick[N]; void upd(int x, int val){ for(int i = x; i < N; i += (i & -i)) fenwick[i] += val; } int get(int x){ int ans = 0; for(int i = x; i >= 1; i -= (i & -i)) ans += fenwick[i]; return ans; } void solve(){ cin >> n; vector<pair<long long, int> > v(n); for(int i = 0; i < n; ++i){ cin >> v[i].first; v[i].second = i; } vector<long long> a(n); sort(v.begin(), v.end()); int ct = 1; a[v[0].second] = ct; for(int i = 1; i < n; ++i){ if(v[i].first != v[i - 1].first) ++ct; a[v[i].second] = ct; } // for(auto k : a) cout << k << ' '; // cout << endl; long long pre[N], suf[N]; for(int i = 0; i < n; ++i){ int x = get(a[i] - 1); upd(a[i], 1); // cout << x << ' '; pre[i] = x; } // cout << endl; memset(fenwick, 0, sizeof fenwick); for(int i = n - 1; i >= 0; --i){ int x = get(a[i] - 1); upd(a[i], 1); suf[i] = x; } long long ans = 0; for(int i = 1; i < n - 1; ++i) ans += (pre[i] * suf[i]); cout << ans << '\n'; } int main() { fast; int t = 1; // cin >> t; while(t--) solve(); return 0; }

Compilation message (stderr)

Mountains.cpp: In function 'int main()':
Mountains.cpp:61:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   61 |     while(t--)
      |     ^~~~~
Mountains.cpp:63:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   63 |  return 0;
      |  ^~~~~~
#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...