Submission #156200

#TimeUsernameProblemLanguageResultExecution timeMemory
156200theboatmanMoney (IZhO17_money)C++11
0 / 100
10 ms8184 KiB
#include <bits/stdc++.h> #define y1 theboatman #define make_struct(args...) {args} using namespace std; const int inf = 1e9 + 10; const int N = 1e6 + 10; struct tree { int n; vector <int> t, f; void init(int temp) { n = temp; t.resize(n); f.resize(n); } void inc(int pos) { if(f[pos])return; f[pos] = 1; for(int i = pos; i <= n; i += i & -i) { t[i] += 1; } } int get(int pos) { int res = 0; for(int i = pos; i > 0; i -= i & -i) { res += t[i]; } return res; } int get(int l, int r) { return get(r) - get(l - 1); } }; int main() { cin.tie(0); ios::sync_with_stdio(0); int n; cin >> n; vector <int> a(n); for(int i = 0; i < n; i++) { cin >> a[i]; } int now = 0, x = 0; while(now < n && x <= a[now]) { x = a[now]; now++; } tree bank; bank.init(N); int l = inf, r = -inf; for(int i = 0; i < now; i++) { bank.inc(a[i]); l = min(l, a[i]); r = max(r, a[i]); } int ans = 0; for(int i = now; i < n; i++) { ans++; if (a[i] >= r) { int x = 0; while(i < n && x <= a[i]) { x = a[i]; l = min(l, a[i]); r = max(r, a[i]); bank.inc(x); i++; } i--; } else { vector <int> lazy; if (a[i] < l) { int x = 0; while(i < n && x <= a[i] && a[i] <= l) { x = a[i]; lazy.push_back(x); i++; } i--; } else { int x = 0; int les = a[i]; while(i < n && x <= a[i] && a[i] <= r) { int pos = bank.get(1, les); int pos1 = bank.get(1, a[i]); //cout << les << " " << *more << " " << pos << " " << pos1 << " " << i << endl; if (pos1 - pos < 1) { x = a[i]; lazy.push_back(x); i++; } else { break; } } i--; } for(auto it : lazy) { bank.inc(it); l = min(l, it); r = max(r, it); } } } cout << ans + 1 << "\n"; return 0; } /* find_by_order(X) k -> элемент, нумерация с нуля order_of_key(X) кол-во < чем X */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...