Submission #884489

#TimeUsernameProblemLanguageResultExecution timeMemory
884489tsumondaiMoney (IZhO17_money)C++14
0 / 100
4 ms22264 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define pb push_back #define mp make_pair #define foru(i, l, r) for(int i = l; i <= r; i++) #define ford(i, r, l) for(int i = r; i >= l; i--) #define __TIME (1.0 * clock() / CLOCKS_PER_SEC) typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 1e6 + 10; const int oo = 1e9, mod = 1e9 + 7; int n, m, k, a[N + 5]; vector<int> bit1(N + 5, 0), bit2(N + 5, 0); int bit[N]; void update(int x) { for (int i = x; i < N; i += i & -i) { bit[i]++; } } int get(int x) { int ans = 0; for (int i = x; i > 0; i -= i & -i) { ans += bit[i]; } return ans; } void updateRange(int l, int r) { for (int i = l; i <= r; i++) { update(a[i]); } } void process() { cin >> n; foru(i, 1, n) cin >> a[i]; int ans = 0, pre = 0; foru(i, 1, n - 1) { if (i < n && a[i] > a[i + 1]) { ans++; updateRange(pre + 1, i); pre = i; continue; } if (a[i] == a[i + 1]) continue; if (get(a[i + 1]) - get(a[pre + 1]) > 0) { ans++; updateRange(pre + 1, i); pre = i; } } cout << ans + 1; return; } signed main() { cin.tie(0)->sync_with_stdio(false); //freopen(".inp", "r", stdin); //freopen(".out", "w", stdout); process(); cerr << "Time elapsed: " << __TIME << " s.\n"; return 0; } // dont stop
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...