Submission #1253894

#TimeUsernameProblemLanguageResultExecution timeMemory
1253894JerMountains (NOI20_mountains)C++20
100 / 100
547 ms107416 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 3e5 + 5; ll h[MAXN]; vector<ll> tree[4 * MAXN]; int n; void build(int v, int l, int r) { if (l == r) return void(tree[v] = {h[l]}); int m = (l + r) / 2; build(2 * v, l, m); build(2 * v + 1, m + 1, r); merge(tree[2 * v].begin(), tree[2 * v].end(), tree[2 * v + 1].begin(), tree[2 * v + 1].end(), back_inserter(tree[v])); } ll query(int v, int l, int r, int ql, int qr, ll val){ if (qr < l or ql > r) return 0LL; if (ql <= l and qr >= r) return (ll)(lower_bound(tree[v].begin(), tree[v].end(), val) - tree[v].begin()); int m = (l + r) / 2; return query(2 * v, l, m, ql, qr, val) + query(2 * v + 1, m + 1, r, ql, qr, val); } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 0; i < n; i++) cin >> h[i]; build(1, 0, n - 1); ll res = 0; for(int i = 1; i < n - 1; i++) res += (query(1, 0, n - 1, 0, i - 1, h[i])) * (query(1, 0, n - 1, i + 1, n - 1, h[i])); cout << res << '\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...