#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0);
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 1e6 + 11;
const int MAX = 1e6;
ll n, res;
ll a[N], t[4 * N];
void upd(ll k, ll x, ll v = 1, ll l = 1, ll r = MAX){
if(l == r){
t[v] += x;
return;
}
ll md = (l + r) / 2;
if(k <= md) upd(k, x, v + v, l, md);
else upd(k, x, v + v + 1, md + 1, r);
t[v] = t[v + v] + t[v + v + 1];
}
ll get(ll tl, ll tr, ll v = 1, ll l = 1, ll r = MAX){
if(r < tl || tr < l) return 0;
if(tl <= l && r <= tr) return t[v];
ll md = (l + r) / 2;
return get(tl, tr, v + v, l, md) + get(tl, tr, v + v + 1, md + 1, r);
}
void sol(){
cin >> n, res = 0;
for(ll i = 1; i <= n; i++) cin >> a[i];
for(ll i = 1; i <= n;){
ll j = i;
while(j <= n && a[j] <= a[j + 1] && get(a[j] + 1, a[j + 1] - 1) == 0) j++;
// cout << i << ' ' << j << '\n';
while(i <= j) upd(a[i], 1), i++;
res++;
}
cout << res;
}
signed main(){
ios
sol();
// slow();
// stress();
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
592 KB |
Output is correct |
| 8 |
Correct |
1 ms |
504 KB |
Output is correct |
| 9 |
Correct |
1 ms |
592 KB |
Output is correct |
| 10 |
Correct |
1 ms |
592 KB |
Output is correct |
| 11 |
Correct |
1 ms |
592 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
592 KB |
Output is correct |
| 8 |
Correct |
1 ms |
504 KB |
Output is correct |
| 9 |
Correct |
1 ms |
592 KB |
Output is correct |
| 10 |
Correct |
1 ms |
592 KB |
Output is correct |
| 11 |
Correct |
1 ms |
592 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
592 KB |
Output is correct |
| 8 |
Correct |
1 ms |
504 KB |
Output is correct |
| 9 |
Correct |
1 ms |
592 KB |
Output is correct |
| 10 |
Correct |
1 ms |
592 KB |
Output is correct |
| 11 |
Correct |
1 ms |
592 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
592 KB |
Output is correct |
| 8 |
Correct |
1 ms |
504 KB |
Output is correct |
| 9 |
Correct |
1 ms |
592 KB |
Output is correct |
| 10 |
Correct |
1 ms |
592 KB |
Output is correct |
| 11 |
Correct |
1 ms |
592 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
