Submission #340308

#TimeUsernameProblemLanguageResultExecution timeMemory
340308apostoldaniel854Mountains (NOI20_mountains)C++14
100 / 100
611 ms29548 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define pb push_back #define dbg(x) cerr << #x << " " << x << "\n" int n; const int MAX_N = 3e5; int aibL[1 + MAX_N], aibR[1 + MAX_N]; ll h[1 + MAX_N]; void upd (int pos, int val, int aib[]) { while (pos <= n) { aib[pos] += val; pos += pos & -pos; } } int qry (int pos, int aib[]) { int ans = 0; while (pos) { ans += aib[pos]; pos -= pos & -pos; } return ans; } int main () { ios::sync_with_stdio (false); cin.tie (0); cout.tie (0); cin >> n; map <ll, int> mp; for (int i = 1; i <= n; i++) cin >> h[i], mp[h[i]]; int nr = 0; for (auto &x : mp) x.second = ++nr; for (int i = 1; i <= n; i++) h[i] = mp[h[i]]; for (int i = 2; i <= n; i++) upd (h[i], 1, aibR); upd (h[1], 1, aibL); ll ans = 0; for (int i = 2; i <= n; i++) { upd (h[i], -1, aibR); ans += 1ll * qry (h[i] - 1, aibL) * qry (h[i] - 1, aibR); upd (h[i], 1, aibL); } cout << ans << "\n"; 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...