Submission #1267289

#TimeUsernameProblemLanguageResultExecution timeMemory
1267289nguyenvietanhMountains (NOI20_mountains)C++20
100 / 100
373 ms40500 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define pii pair<int,int> #define inp(name) freopen(name, "r", stdin); #define out(name) freopen(name, "w", stdout); const int N = 3e5 + 5; const int mod = 998244353; int n, cur = 0; int a[N], ans[N], tree[N]; void update(int u, int v){ while (u <= cur){ tree[u] += v; u += (u & -u); } } int get(int u){ int ans = 0; while (u > 0){ ans += tree[u]; u -= (u & -u); } return ans; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; set <int> s; map <int, int> m; for (int i = 1; i <= n; i ++){ cin >> a[i]; s.insert(a[i]); ans[i] = 1; } for (auto i : s) m[i] = ++cur; for (int i = 1; i <= n; i ++) a[i] = m[a[i]]; for (int i = 1; i <= n; i ++){ ans[i] *= get(a[i] - 1); update(a[i], 1); } for (int i = 0; i <= cur; i ++) tree[i] = 0; int res = 0; for (int i = n; i >= 1; i --){ ans[i] *= get(a[i] - 1); update(a[i], 1); res += ans[i]; } cout<< res; }
#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...