Submission #1086110

#TimeUsernameProblemLanguageResultExecution timeMemory
1086110duytuandao21Po (COCI21_po)C++17
10 / 70
1060 ms4700 KiB
#include<bits/stdc++.h> using namespace std; const int N = 2e6 + 7; const int inf = 1e9 + 7; const long long infll = 1e18 + 7; int n; int bit[N], a[N]; pair<int, int> b[N]; void update(int x, int v) { while (x <= n) { bit[v] = max(bit[v], v); x += (x & -x); } } int get(int l, int r) { int ans = 0; while (l <= r) { if (r - (r & -r) >= l) { ans = max(ans, bit[r]); r -= (r & -r); } else { ans = max(ans, a[r]); r--; } } return ans; } 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]; update(i, a[i]); b[i] = make_pair(a[i], i); } sort (b + 1, b + 1 + n); int res = 0; for (int i = 1; i <= n; i++) { if (b[i].first != b[i - 1].first) res++; else { if (get(b[i - 1].second, b[i].second) < b[i].first) res++; } } cout << res; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...