Submission #1064615

#TimeUsernameProblemLanguageResultExecution timeMemory
1064615aufanMoney (IZhO17_money)C++17
0 / 100
5 ms8284 KiB
#include <bits/stdc++.h> #define int long long #define fi first #define se second using namespace std; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector<int> a(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; vector<int> fen(1000001); auto upd = [&](int x, int val) { for (; x <= n; x += x & -x) fen[x] += val; }; auto qry = [&](int x) { int res = 0; for (; x > 0; x -= x & -x) res += fen[x]; return res; }; int j = 1; vector<int> dp(n + 1); for (int i = 1; i <= n; i++) { if (a[i] < a[i - 1]) { while (j < i) { upd(a[j++], 1); } } while (j < i && qry(a[i] - 1) - qry(a[j]) > 0) { upd(a[j++], 1); } dp[i] = dp[j - 1] + 1; } cout << dp[n] << '\n'; 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...