Submission #680895

#TimeUsernameProblemLanguageResultExecution timeMemory
680895DennisTranMountains (NOI20_mountains)C++17
100 / 100
161 ms14340 KiB
#pragma GCC optimize("O2") #pragma GCC target("avx,avx2,fma") #include <bits/stdc++.h> #define FOR(i, a, b) for (int i = (a); i <= (b); i++) #define FOD(i, a, b) for (int i = (a); i >= (b); i--) #define REP(i, n) for (int i = 0; i < (n); i++) #define ALL(x) (x).begin(), (x).end() #define TIME (1.0 * clock() / CLOCKS_PER_SEC) #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } using namespace std; const int MAXN = 3e5 + 5; int N, L[MAXN], R[MAXN]; vector <long long> nen; long long a[MAXN]; struct BIT{ int bit[MAXN]; void upd(int x, int val) {for (; x <= N; x += x &-x) bit[x] += val;} int get(int x) { int ans = 0; for (; x; x -= x&-x) ans += bit[x]; return ans; } } mybit; void calc(int *val) { FOR(i, 1, N) { val[i] = mybit.get(a[i] - 1); mybit.upd(a[i], 1); } FOR(i, 1, N) { mybit.upd(a[i], -1); } } signed main(void) { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); //file("TASK"); cin >> N; FOR(i, 1, N) cin >> a[i], nen.emplace_back(a[i]); sort(ALL(nen)); nen.erase(unique(ALL(nen)), nen.end()); FOR(i, 1, N) a[i] = lower_bound(ALL(nen), a[i]) - nen.begin() + 1; calc(L); reverse(a + 1, a + N + 1); calc(R); reverse(R + 1, R + N + 1); long long ans = 0; FOR(i, 1, N) ans += 1ll * L[i] * R[i]; cout << ans; cerr << "Time elapsed: " << TIME << " s.\n"; return (0 ^ 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...