#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);
}
};
vector<int> add(vector<int> a, vector<int> b) {
if (a.empty()) return b;
if (b.back() <= a[0]) {
for (int x: a) b.emplace_back(x);
return b;
}
if (a.back() <= b[0]) {
for (int x: b) a.emplace_back(x);
return a;
}
for (int i = 1; i < a.size(); i++) {
if (a[i - 1] <= b[0] and b.back() <= a[i]) {
vector<int> v;
for (int j = 0; j < i; j++) v.emplace_back(a[j]);
for (int x: b) v.emplace_back(x);
for (int j = i; j < a.size(); j++) v.emplace_back(a[j]);
return v;
}
}
return {};
}
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];
// SegTree sg; sg.init(N);
vector<int> ans, now = {a[1]};
int cnt = 1;
for (int i = 2; i <= n; i++) {
if (a[i] < now.back()) {
ans = add(ans, now);
cnt++;
now = {a[i]};
continue;
}
now.emplace_back(a[i]);
auto v = add(ans, now);
if (v.empty()) {
for (int j = 1; j < now.size(); j++) ans.emplace_back(now[j - 1]);
now = {a[i]};
cnt++;
}
}
cout << cnt;
}
Compilation message
money.cpp: In function 'std::vector<int> add(std::vector<int>, std::vector<int>)':
money.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int i = 1; i < a.size(); i++) {
| ~~^~~~~~~~~~
money.cpp:60:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int j = i; j < a.size(); j++) v.emplace_back(a[j]);
| ~~^~~~~~~~~~
money.cpp: In function 'int main()':
money.cpp:91:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for (int j = 1; j < now.size(); j++) ans.emplace_back(now[j - 1]);
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
