#include <bits/stdc++.h>
using namespace std;
vector<int> wow(1000001);
vector<int> br(1000001);
set<int> pos;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
vector<int> haha(n);
for(int i = 0; i < n; i++) {
cin >> haha[i];
}
pos.insert(-1);
for(int i = 0; i < n; i++) {
pos.insert(i);
}
vector<pair<int,int>> wut(n);
for(int i = 0; i < n; i++) {
wut[i] = {haha[i],i};
}
sort(wut.begin(),wut.end());
for(int i = n-1; i >= 0; i--) {
wow[wut[i].first] = i;
}
int y = n-1,ans = 0;
while(y >= 0) {
int p = wow[haha[y]]-1+br[haha[y]];
for(int i = y; i >= 0; i--) {
if(haha[i] != haha[y]) {
break;
}
br[haha[y]]++;
p++;
}
while(y >= 0 && p >= 0 && wut[p].first == haha[y]) {
y--;
pos.erase(p);
p = *(--pos.upper_bound(p));
}
ans++;
}
cout << ans;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 3 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 4 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 5 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 6 |
Correct |
3 ms |
8284 KB |
Output is correct |
| 7 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 8 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 9 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 10 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 11 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 12 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 13 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 14 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 15 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 16 |
Correct |
2 ms |
8284 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 3 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 4 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 5 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 6 |
Correct |
3 ms |
8284 KB |
Output is correct |
| 7 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 8 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 9 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 10 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 11 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 12 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 13 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 14 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 15 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 16 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 17 |
Correct |
2 ms |
8536 KB |
Output is correct |
| 18 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 19 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 20 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 21 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 22 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 23 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 24 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 25 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 26 |
Correct |
2 ms |
8284 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 3 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 4 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 5 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 6 |
Correct |
3 ms |
8284 KB |
Output is correct |
| 7 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 8 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 9 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 10 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 11 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 12 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 13 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 14 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 15 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 16 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 17 |
Correct |
2 ms |
8536 KB |
Output is correct |
| 18 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 19 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 20 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 21 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 22 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 23 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 24 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 25 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 26 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 27 |
Correct |
3 ms |
8284 KB |
Output is correct |
| 28 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 29 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 30 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 31 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 32 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 33 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 34 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 35 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 36 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 37 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 38 |
Correct |
2 ms |
8284 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 3 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 4 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 5 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 6 |
Correct |
3 ms |
8284 KB |
Output is correct |
| 7 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 8 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 9 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 10 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 11 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 12 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 13 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 14 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 15 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 16 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 17 |
Correct |
2 ms |
8536 KB |
Output is correct |
| 18 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 19 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 20 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 21 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 22 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 23 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 24 |
Correct |
2 ms |
8280 KB |
Output is correct |
| 25 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 26 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 27 |
Correct |
3 ms |
8284 KB |
Output is correct |
| 28 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 29 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 30 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 31 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 32 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 33 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 34 |
Correct |
3 ms |
8280 KB |
Output is correct |
| 35 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 36 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 37 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 38 |
Correct |
2 ms |
8284 KB |
Output is correct |
| 39 |
Correct |
243 ms |
36692 KB |
Output is correct |
| 40 |
Correct |
473 ms |
54600 KB |
Output is correct |
| 41 |
Correct |
179 ms |
30872 KB |
Output is correct |
| 42 |
Correct |
178 ms |
28240 KB |
Output is correct |
| 43 |
Correct |
121 ms |
22356 KB |
Output is correct |
| 44 |
Correct |
557 ms |
67152 KB |
Output is correct |
| 45 |
Correct |
515 ms |
67088 KB |
Output is correct |
| 46 |
Correct |
530 ms |
66896 KB |
Output is correct |
| 47 |
Correct |
475 ms |
67000 KB |
Output is correct |
| 48 |
Correct |
479 ms |
66988 KB |
Output is correct |
| 49 |
Correct |
808 ms |
66988 KB |
Output is correct |
| 50 |
Correct |
824 ms |
73880 KB |
Output is correct |
| 51 |
Correct |
882 ms |
73556 KB |
Output is correct |
| 52 |
Correct |
780 ms |
73760 KB |
Output is correct |
| 53 |
Correct |
858 ms |
73992 KB |
Output is correct |
| 54 |
Correct |
829 ms |
73464 KB |
Output is correct |
| 55 |
Correct |
1350 ms |
73732 KB |
Output is correct |
| 56 |
Correct |
1347 ms |
73736 KB |
Output is correct |
| 57 |
Correct |
1294 ms |
73972 KB |
Output is correct |
| 58 |
Correct |
1404 ms |
73732 KB |
Output is correct |
| 59 |
Correct |
1416 ms |
73632 KB |
Output is correct |
| 60 |
Correct |
1469 ms |
73740 KB |
Output is correct |
| 61 |
Correct |
1424 ms |
73732 KB |
Output is correct |
| 62 |
Correct |
1348 ms |
73732 KB |
Output is correct |
