Submission #906922

#TimeUsernameProblemLanguageResultExecution timeMemory
906922daoquanglinh2007Money (IZhO17_money)C++17
100 / 100
1303 ms58308 KiB
#include <bits/stdc++.h> using namespace std; const int NM = 1e6, inf = 1e9+7; int N, a[NM+5], ans = 0; set <int> S; set <int>::iterator it; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; for (int i = 1; i <= N; i++) cin >> a[i]; for (int i = 1; i <= N; i++){ int j = i, l, r; if (S.empty()) l = -inf, r = +inf; else if (a[i] < *S.begin()) l = -inf, r = *S.begin(); else if (a[i] >= *(--S.end())) l = *(--S.end()), r = +inf; else{ it = S.upper_bound(a[i]); r = *it; it--; l = *it; } while (j <= N && a[j] >= l && a[j] <= r){ S.insert(a[j]); l = a[j]; j++; } ans++; i = j-1; } cout << ans; 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...