Submission #84358

#TimeUsernameProblemLanguageResultExecution timeMemory
84358zoooma13Baloni (COCI15_baloni)C++14
100 / 100
1375 ms89148 KiB
#include <bits/stdc++.h> using namespace std; #define MAX_N 1000006 inline int GI() { int GIR = 0; char GIC = getchar(); while(GIC < '0' || '9' < GIC) GIC = getchar(); while('0' <= GIC && GIC <= '9') { GIR = (GIR * 10) + (GIC - '0'); GIC = getchar(); } return GIR; } int N ,A; set<int> ss[MAX_N]; int cnt[MAX_N]; vector <int> nxt; int main() { N = GI(); for(int i=0; i<N; i++) { A = GI(); ss[A].insert(i); if(!cnt[A]++) nxt.push_back(A); } sort(nxt.begin() ,nxt.end()); int Ans = 0 ,pt = nxt.size()-1; while(~pt) { int i = nxt[pt] ,j = -1; while(true) { auto it = ss[i].upper_bound(j); if(it == ss[i].end()) break; j = *it; ss[i].erase(it); --cnt[i--]; } while(~pt && !cnt[nxt[pt]]) pt--; Ans++; } cout << Ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...