Submission #439054

#TimeUsernameProblemLanguageResultExecution timeMemory
439054meatrowMountains (NOI20_mountains)C++17
100 / 100
1494 ms46940 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int MOD = 998244353; ll binpow(ll a, ll p, int mod = MOD) { ll res = 1; while (p) { if (p & 1) { (res *= a) %= mod; } p >>= 1; (a *= a) %= mod; } return res; } ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } const int N = 3e5 + 5; int fenw[N]; void add(int pos) { for (; pos < N; pos |= pos + 1) { fenw[pos]++; } } ll get(int pos) { ll res = 0; for (; pos >= 0; pos = (pos & (pos + 1)) - 1) { res += fenw[pos]; } return res; } void solve() { int n; cin >> n; vector<ll> h(n); set<ll> setik; for (int i = 0; i < n; i++) { cin >> h[i]; setik.insert(h[i]); } int cur = 0; map<ll, int> id; for (ll val : setik) { id[val] = cur++; } vector<ll> l(n), r(n); for (int i = 0; i < n; i++) { l[i] = get(id[h[i]] - 1); add(id[h[i]]); } fill(fenw, fenw + N, 0); for (int i = n - 1; i >= 0; i--) { r[i] = get(id[h[i]] - 1); add(id[h[i]]); } ll ans = 0; for (int i = 0; i < n; i++) { ans += l[i] * r[i]; } cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T = 1; // cin >> T; for (int tc = 1; tc <= T; tc++) { // cout << "Case #" << tc << ": "; solve(); } 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...