Submission #830144

#TimeUsernameProblemLanguageResultExecution timeMemory
830144NK_Mountains (NOI20_mountains)C++17
100 / 100
146 ms9744 KiB
// Success consists of going from failure to failure without loss of enthusiasm #include <bits/stdc++.h> using namespace std; #define nl '\n' #define pb push_back #define mp make_pair #define f first #define s second #define sz(x) int(x.size()) template<class T> using V = vector<T>; using vi = V<int>; using ll = long long; using pi = pair<int, int>; using vpi = V<pi>; using vl = V<ll>; using db = long double; const int INF = 1e9 + 10; struct BIT { int N; vl A; void init(int n) { N = n; A = vl(N, 0); } void upd(int p, int x) { for(++p;p<=N;p+=p&-p) A[p-1] += x; } ll sum(int l, int r) { return sum(r + 1) - sum(l); } ll sum(int r) { ll s = 0; for(;r;r-=r&-r) s += A[r-1]; return s; } }; int main() { cin.tie(0)->sync_with_stdio(0); int N; cin >> N; vl A(N); for(auto& x : A) cin >> x; vl X = A; sort(begin(X), end(X)); X.erase(unique(begin(X), end(X)), end(X)); for(auto& x : A) x = lower_bound(begin(X), end(X), x) - begin(X); int M = sz(X); BIT up, dwn; up.init(M); dwn.init(M); ll ans = 0; for(auto& x : A) { ans += dwn.sum(x + 1, M - 1); ll DWN = up.sum(0, x - 1); dwn.upd(x, DWN); up.upd(x, 1); } cout << ans << nl; 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...