Submission #332112

#TimeUsernameProblemLanguageResultExecution timeMemory
332112SaraMountains (NOI20_mountains)C++14
100 / 100
474 ms31200 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long int #define F first #define S second #define pb push_back #define lc (ind * 2) #define rc (lc + 1) #define md ((b + e) / 2) const ll N = 3e5 + 5; const ll LOG = 20; const int MOD = 1e9 + 7; const ll INF = 1e18 + 10; int n, cnt[4 * N]; ll H[N], ans; vector <int> all[N]; vector <ll> vc; void add(int id, int b = 0, int e = n, int ind = 1){ if (b + 1 == e){ cnt[ind] ++; return; } if (id < md) add(id, b, md, lc); else add(id, md, e, rc); cnt[ind] = cnt[lc] + cnt[rc]; return; } int get(int l, int r, int b = 0, int e = n, int ind = 1){ if (l <= b && e <= r){ return cnt[ind]; } int res = 0; if (l < md) res += get(l, r, b, md, lc); if (md < r) res += get(l, r, md, e, rc); return res; } int main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n; for (int i = 0; i < n; i++){ cin >> H[i]; vc.pb(H[i]); } sort(vc.begin(), vc.end()); vc.resize(unique(vc.begin(), vc.end()) - vc.begin()); for (int i = 0; i < n; i++){ int p = lower_bound(vc.begin(), vc.end(), H[i]) - vc.begin(); all[p].pb(i); } for (int i = 0; i < (int)vc.size(); i++){ ll L, R; for (int j : all[i]){ L = 0; R = 0; if (j) L = get(0, j); R = get(j, n); ans += (L * R); } for (int j : all[i]){ add(j); } } 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...