Submission #680222

#TimeUsernameProblemLanguageResultExecution timeMemory
680222raysh07Mountains (NOI20_mountains)C++17
100 / 100
703 ms52880 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define INF (int)1e18 mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); int n; const int maxn = 3e5 + 69; int a[maxn]; set <int> send; map <int, int> comp; int seg[4*maxn]; int b[maxn]; void Update(int l, int r, int pos, int qpos, int qval){ seg[pos]+=qval; if (l==r) return; int mid = (l+r)/2; if (qpos<=mid) Update(l, mid, pos*2, qpos, qval); else Update(mid + 1, r, pos*2 + 1, qpos, qval); } int Query(int l, int r, int pos, int ql, int qr){ if (l>=ql && r<=qr) return seg[pos]; else if (l>qr || r<ql) return 0; int mid = (l+r)/2; return Query(l, mid, pos*2, ql, qr) + Query(mid + 1, r, pos*2 + 1, ql, qr); } void compress() { int p = 1; for (auto x: send){ comp[x] = p++; } } void Solve() { cin>>n; for (int i=1; i<=n; i++){ cin>>a[i]; send.insert(a[i]); } compress(); for (int i=1; i<=n; i++) a[i] = comp[a[i]]; for (int i=1; i<=n; i++){ b[i] = Query(1, n, 1, 1, a[i]-1); Update(1, n, 1, a[i], 1); } for (int i=0; i<4*maxn; i++) seg[i] = 0; int sum = 0; for (int i=n; i>=1; i--){ b[i] *= Query(1, n, 1, 1, a[i]-1); Update(1, n, 1, a[i], 1); sum += b[i]; } cout<<sum; } int32_t main() { auto begin = std::chrono::high_resolution_clock::now(); ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; for(int i = 1; i <= t; i++) { //cout << "Case #" << i << ": "; Solve(); } auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\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...