Submission #1112865

#TimeUsernameProblemLanguageResultExecution timeMemory
1112865adiyerMoney (IZhO17_money)C++17
0 / 100
2 ms12624 KiB
#include <bits/stdc++.h> #define ios ios_base::sync_with_stdio(0); cin.tie(0); #define pb push_back using namespace std; typedef long long ll; const int N = 1e6 + 11; const int MAX = 1e6; ll n, res; ll a[N], t[4 * N]; void upd(ll k, ll x, ll v = 1, ll l = 1, ll r = MAX){ if(l == r){ t[v] += x; return; } ll md = (l + r) / 2; if(k <= md) upd(k, x, v + v, l, md); else upd(k, x, v + v + 1, md + 1, r); t[v] = t[v + v] + t[v + v + 1]; } ll get(ll tl, ll tr, ll v = 1, ll l = 1, ll r = MAX){ if(r < tl || tr < l) return 0; if(tl <= l && r <= tr) return t[v]; ll md = (l + r) / 2; return get(tl, tr, v + v, l, md) + get(tl, tr, v + v + 1, md + 1, r); } void sol(){ cin >> n, res = 0; for(ll i = 1; i <= n; i++) cin >> a[i]; for(ll i = 1; i <= n;){ ll j = i; while(j < n && a[j] <= a[j + 1] && get(a[j] + 1, a[j + 1] - 1) == 0) j++; // cout << i << ' ' << j << '\n'; while(i <= j) upd(a[i], 1), i++; res++; } cout << res; } signed main(){ ios sol(); // slow(); // stress(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...