Submission #706588

#TimeUsernameProblemLanguageResultExecution timeMemory
706588Shreyan_PaliwalMoney (IZhO17_money)C++17
0 / 100
0 ms340 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6; int n; int a[maxn + 5]; int bit[maxn + 1]; void upd(int k, int v) { for ( ; k <= maxn; k += (k & -k)) bit[k] += v; } int qry(int k) { int ret = 0; for (; k; k -= (k & -k)) ret += bit[k]; return ret; } int main() { // freopen("main.in", "r", stdin); cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; // figure out nondecreasing sequences int l = 0; int ans = 0; for (int i = 0; i < n; i++) { if (i == n - 1 || a[i + 1] < a[i]) { // [l, i] int L = l; for (int j = l + 1; j <= i; j++) { // cout << l << ' ' << i << ' ' << L << ' ' << j << endl; // cout << qry(a[j]-1) << ' ' << qry(a[L]-1) << endl; if (qry(a[j] - 1) - qry(a[L])) { ans++; L = j + 1; } } for (int k = L; k <= i; k++) { upd(a[k], 1); } ans++; l = i + 1; } } cout << ans << endl; 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...