Submission #143674

#TimeUsernameProblemLanguageResultExecution timeMemory
143674MladenPMoney (IZhO17_money)C++17
0 / 100
2 ms376 KiB
#include <bits/stdc++.h> #define MAXN 1000010 #define pii pair<int,int> #define pb push_back #define fi first #define se second using namespace std; int a[MAXN], b[MAXN], inv[MAXN], N, l, r; int R[MAXN]; vector<pii> seg; int main() { cin >> N; for(int i = 1; i <= N; i++) cin >> a[i]; for(int i = 1; i <= N; i++) b[i-1] = a[i]; sort(b, b+N); for(int i = 0; i < N; i++) inv[b[i]] = i+1; for(int i = 1; i <= N; i++) a[i] = inv[a[i]]; l = r = a[1]; for(int i = 2; i <= N+1; i++) { if(a[i] == r+1) { r++; } else { seg.pb({l, r}); l = r = a[i]; } } int rez = 0; while(!seg.empty()) { pii vrh = seg.back(); seg.pop_back(); l = vrh.fi, r = vrh.se; if(r == N+1) { R[l] = r; continue; } if(R[r+1]) { r = R[r+1]; R[r+1] = 0; seg.pb({l, r}); } else { rez++; R[l] = r; } } cout << rez; 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...