Submission #1227554

#TimeUsernameProblemLanguageResultExecution timeMemory
1227554overwatch9Mountains (NOI20_mountains)C++20
100 / 100
630 ms37988 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; struct stree { #define lc v*2 #define rc v*2+1 vector <int> tree; stree (int s) { tree.resize(s*4); } void pushup(int v) { tree[v] = tree[lc] + tree[rc]; } void update(int v, int tl, int tr, int p) { if (tl > p || tr < p) return; if (tl == tr) { tree[v] = 1; return; } int tm = (tl + tr) / 2; update(lc, tl, tm, p); update(rc, tm+1, tr, p); pushup(v); } int query(int v, int tl, int tr, int l, int r) { if (tl > r || tr < l) return 0; if (tl >= l && tr <= r) return tree[v]; int tm = (tl + tr) / 2; int a = query(lc, tl, tm, l, r); int b = query(rc, tm+1, tr, l, r); return a + b; } }; int main() { int n; cin >> n; map <ll, vector <int>> mp; for (int i = 0; i < n; i++) { ll x; cin >> x; mp[x].push_back(i); } stree tree(n); ll ans = 0; for (auto it : mp) { for (auto i : it.second) { ll l = tree.query(1, 0, n, 0, i); ll r = tree.query(1, 0, n, i, n); ans += l * r; } for (auto i : it.second) { tree.update(1, 0, n, i); } } cout << ans << '\n'; }
#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...