Submission #1167929

#TimeUsernameProblemLanguageResultExecution timeMemory
1167929SG2AlokMoney (IZhO17_money)C++20
100 / 100
553 ms70912 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; typedef long long ll; using namespace __gnu_pbds; #define endl '\n' #define hitaf ios_base::sync_with_stdio(false); cin.tie(0); #define fi first #define se second template <typename T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag, tree_order_statistics_node_update>; const ll MOD = 1e9 + 7; const ll MOD1 = 998244353; const ll INF = 4500000000000000000LL; const ll mod1 = 6900000469; const ll mod2 = 698000002369; ll n, m, q, k, a[1200005], b[500005], c[500005], st[2000005], lazy[2000005]; string s, s1, s2; int main(){ hitaf int T = 1; // cin >> T; while(T--){ cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; vector<ll> dp(n + 2, INF), nxt(n + 2); dp[0] = 0; multiset<ll> ms; for(int i = 1; i <= n; i++){ if(ms.empty()){ dp[i] = 1; ms.insert(a[i]); nxt[i] = INF; } else if(a[i] < a[i - 1]){ dp[i] = dp[i - 1] + 1; ms.insert(a[i]); nxt[i] = *ms.upper_bound(a[i]); } else { if(nxt[i - 1] == a[i]){ dp[i] = dp[i - 1]; nxt[i] = a[i]; } else if(a[i] < nxt[i - 1]){ dp[i] = dp[i - 1]; nxt[i] = nxt[i - 1]; } else { dp[i] = dp[i - 1] + 1; auto pos = ms.upper_bound(a[i]); if(pos == ms.end()){ nxt[i] = INF; } else { nxt[i] = *pos; } } ms.insert(a[i]); } } cout << dp[n] << endl; } return 0; } /* dp[i][j] = */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...