#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int inf = 1e9;
const int N = 1e6 + 5;
struct SegTree {
vector<int> tree;
int size;
void init(int n) {
size = 1;
while (size < n) size <<= 1;
tree.assign(2 * size, 0);
}
void update(int i, int v, int x, int l, int r) {
if (r - l == 1) {
tree[x] += v;
return;
}
int m = (l + r) >> 1;
if (i < m) update(i, v, x << 1, l, m);
else update(i, v, x << 1 | 1, m, r);
tree[x] = tree[x << 1] + tree[x << 1 | 1];
}
void update(int i, int v) {
assert(i < size);
update(i, v, 1, 0, size);
}
int find_bigger(int k, int x, int l, int r) {
if (r - l == 1) return l;
int m = (l + r) >> 1;
if (tree[x << 1] >= k) return find_bigger(k, x << 1, l, m);
else return find_bigger(k - tree[x << 1], x << 1 | 1, m, r);
}
int find_bigger(int k) {
return find_bigger(k, 1, 0, size);
}
};
struct Fenwick {
vector<int> tree;
int len;
void init(int n) {
len = n;
tree.assign(len + 1, 0);
}
void update(int i, int v) {
i++;
while (i <= len) {
tree[i] += v;
i += i & (-i);
}
}
int get(int i) {
i++;
int sum = 0;
while (i > 0) {
sum += tree[i];
i -= i & (-i);
}
return sum;
}
int get(int l, int r) {
return get(r) - get(l - 1);
}
};
int main() {
cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
Fenwick fw; fw.init(N);
int cnt = 1;
for (int l = 1, r = 2; r <= n; r++) {
if (a[r] < a[r - 1]) {
for (int i = l; i < r; i++) fw.update(a[i], 1);
l = r;
cnt++;
continue;
}
int lx = fw.get(a[l]), rx = fw.get(a[r] - 1) + 1;
if (rx - lx > 1) {
for (int i = l; i < r; i++) fw.update(a[i], 1);
l = r;
cnt++;
}
}
cout << cnt;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 12 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 13 |
Correct |
3 ms |
4188 KB |
Output is correct |
| 14 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 15 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 16 |
Correct |
1 ms |
4188 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 12 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 13 |
Correct |
3 ms |
4188 KB |
Output is correct |
| 14 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 15 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 16 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 17 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 18 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 19 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 20 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 21 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 22 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 23 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 24 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 25 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 26 |
Correct |
1 ms |
4188 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 12 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 13 |
Correct |
3 ms |
4188 KB |
Output is correct |
| 14 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 15 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 16 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 17 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 18 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 19 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 20 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 21 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 22 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 23 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 24 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 25 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 26 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 27 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 28 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 29 |
Correct |
2 ms |
4188 KB |
Output is correct |
| 30 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 31 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 32 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 33 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 34 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 35 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 36 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 37 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 38 |
Correct |
1 ms |
4188 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 12 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 13 |
Correct |
3 ms |
4188 KB |
Output is correct |
| 14 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 15 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 16 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 17 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 18 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 19 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 20 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 21 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 22 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 23 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 24 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 25 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 26 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 27 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 28 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 29 |
Correct |
2 ms |
4188 KB |
Output is correct |
| 30 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 31 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 32 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 33 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 34 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 35 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 36 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 37 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 38 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 39 |
Correct |
45 ms |
6168 KB |
Output is correct |
| 40 |
Correct |
90 ms |
12624 KB |
Output is correct |
| 41 |
Correct |
37 ms |
8240 KB |
Output is correct |
| 42 |
Correct |
35 ms |
8032 KB |
Output is correct |
| 43 |
Correct |
28 ms |
6920 KB |
Output is correct |
| 44 |
Correct |
105 ms |
14932 KB |
Output is correct |
| 45 |
Correct |
109 ms |
14712 KB |
Output is correct |
| 46 |
Correct |
103 ms |
14968 KB |
Output is correct |
| 47 |
Correct |
91 ms |
14964 KB |
Output is correct |
| 48 |
Correct |
91 ms |
15108 KB |
Output is correct |
| 49 |
Correct |
118 ms |
15224 KB |
Output is correct |
| 50 |
Correct |
101 ms |
14840 KB |
Output is correct |
| 51 |
Correct |
100 ms |
14840 KB |
Output is correct |
| 52 |
Correct |
99 ms |
15060 KB |
Output is correct |
| 53 |
Correct |
105 ms |
15184 KB |
Output is correct |
| 54 |
Correct |
104 ms |
14672 KB |
Output is correct |
| 55 |
Correct |
107 ms |
14856 KB |
Output is correct |
| 56 |
Correct |
115 ms |
14932 KB |
Output is correct |
| 57 |
Correct |
110 ms |
14932 KB |
Output is correct |
| 58 |
Correct |
108 ms |
15004 KB |
Output is correct |
| 59 |
Correct |
111 ms |
15004 KB |
Output is correct |
| 60 |
Correct |
106 ms |
14928 KB |
Output is correct |
| 61 |
Correct |
109 ms |
15004 KB |
Output is correct |
| 62 |
Correct |
106 ms |
15000 KB |
Output is correct |
