Submission #888926

#TimeUsernameProblemLanguageResultExecution timeMemory
888926vjudge1Mountains (NOI20_mountains)C++17
100 / 100
84 ms17840 KiB
/* #pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt") */ #include <bits/stdc++.h> #define taskname "" #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define i64 long long #define pb push_back #define ff first #define ss second #define isz(x) (int)x.size() using namespace std; const int mxN = 3e5 + 5; const int mod = 1e9 + 7; const i64 oo = 1e18; struct FenwickTree { int n; vector<int> data; FenwickTree(int n) : n(n), data(n + 1) {} void update(int idx, int val) { for (; idx <= n; idx += idx & -idx) data[idx] += val; } int get(int idx) { int res = 0; for (; idx > 0; idx -= idx & -idx) res += data[idx]; return res; } }; int n; i64 res, a[mxN]; vector<pair<i64, int>> v; void solve() { cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; v.emplace_back(a[i], i); } sort(all(v)); FenwickTree fenw(n); for (int i = 0; i < n;) { int ptr = i; while (ptr < n && v[ptr].ff == v[i].ff) { int lt = fenw.get(v[ptr].ss), rt = i - lt; res += 1ll * lt * rt; ++ptr; } for (int j = i; j < ptr; ++j) fenw.update(v[j].ss, 1); i = ptr; } cout << res << endl; } signed main() { #ifndef CDuongg if(fopen(taskname".inp", "r")) assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout)); #else freopen("bai3.inp", "r", stdin); freopen("bai3.out", "w", stdout); auto start = chrono::high_resolution_clock::now(); #endif ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; //cin >> t; while(t--) solve(); #ifdef CDuongg auto end = chrono::high_resolution_clock::now(); cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '='; cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl; cout << "Check array size pls sir" << endl; #endif }
#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...