#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>v;
struct SegmentTree{
vector<pair<int, int>>sTree;
void init(int n){
sTree.resize(4 * n);
}
void Build(int node, int l, int r, vector<int>&v){
if(l == r){
sTree[node] = {v[l], v[l]};
}
else{
int mid = (l + r) >> 1;
Build(node * 2, l, mid, v);
Build(node * 2 + 1, mid + 1, r, v);
sTree[node] = {min(sTree[node * 2].first, sTree[node * 2 + 1].first), max(sTree[node * 2].second, sTree[node * 2 + 1].second)};
}
}
int Min_Query(int node, int l, int r, int ql, int qr){
if(ql <= l && r <= qr){
return sTree[node].first;
}
if(ql > r || l > qr)return 1e9;
int mid = (l + r) >> 1;
int lc = Min_Query(node * 2, l, mid, ql, qr);
int rc = Min_Query(node * 2 + 1, mid + 1, r, ql, qr);
return min(lc, rc);
}
int Max_Query(int node, int l, int r, int ql, int qr){
if(ql <= l && r <= qr){
return sTree[node].second;
}
if(ql > r || l > qr)return 0;
int mid = (l + r) >> 1;
int lc = Max_Query(node * 2, l, mid, ql, qr);
int rc = Max_Query(node * 2 + 1, mid + 1, r, ql, qr);
return max(lc, rc);
}
};
struct MergeSortTree{
vector<vector<int>>mTree;
void init(int n){
mTree.resize(4 * n);
}
vector<int> Merge(vector<int>&left, vector<int>&right){
vector<int>res;
int p1 = 0, p2 = 0;
while(p1 < left.size() || p2 < right.size()){
if(p1 == left.size()){
res.push_back(right[p2++]);
}
else if(p2 == right.size()){
res.push_back(left[p1++]);
}
else if(left[p1] > right[p2]){
res.push_back(right[p2++]);
}
else{
res.push_back(left[p1++]);
}
}
return res;
}
void Build(int node, int l, int r, vector<int>&v){
if(l == r){
mTree[node].push_back(v[l]);
}
else{
int mid = (l + r) >> 1;
Build(node * 2, l, mid, v);
Build(node * 2 + 1, mid + 1, r, v);
mTree[node] = Merge(mTree[node * 2], mTree[node * 2 + 1]);
}
}
int Query(int node, int l, int r, int ql, int qr, int num1, int num2){
if(ql <= l && r <= qr){
auto itr1 = upper_bound(mTree[node].begin(), mTree[node].end(), num1);
auto itr2 = lower_bound(mTree[node].begin(), mTree[node].end(), num2);
itr2--;
int pos1 = itr1 - mTree[node].begin();
int pos2 = itr2 - mTree[node].begin();
return max(0, pos2 - pos1 + 1);
}
if(ql > r || l > qr)return 0;
int mid = (l + r) >> 1;
int lc = Query(node * 2, l, mid, ql, qr, num1, num2);
int rc = Query(node * 2 + 1, mid + 1, r, ql, qr, num1, num2);
return lc + rc;
}
};
SegmentTree tree;
MergeSortTree mtree;
/*
6
3 6 4 5 1 2
*/
const int mxN = 1e6 + 6;
int dp[mxN];
int rec(int indx){
int res = 1e9, mn = 1e9, mx = 0;
if(indx == n + 1)return 0;
if(dp[indx] != -1)return dp[indx];
for(int i = indx;i <= n;++i){
mn = min(mn, v[i]);
mx = max(mx, v[i]);
int MN = tree.Min_Query(1, 1, n, 1, indx - 1), MX = tree.Max_Query(1, 1, n, 1, indx - 1);
int cnt = mtree.Query(1, 1, n, 1, indx - 1, mn, mx);
if(mn > MX || MN > mx || cnt == 0)res = min(res, rec(i + 1) + 1);
else break;
}
return dp[indx] = res;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
v.resize(n + 1);
tree.init(n);
mtree.init(n);
for(int i = 1;i <= n;++i){
cin >> v[i];
}
for(int i = 0;i < mxN;++i){
dp[i] = -1;
}
tree.Build(1, 1, n, v);
mtree.Build(1, 1, n, v);
int res = 1e9;
for(int i = 1;i <= n;++i){
if(v[i] < v[i - 1])break;
res = min(res, rec(i + 1) + 1);
}
cout << res;
}
Compilation message
money.cpp: In member function 'std::vector<int> MergeSortTree::Merge(std::vector<int>&, std::vector<int>&)':
money.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | while(p1 < left.size() || p2 < right.size()){
| ~~~^~~~~~~~~~~~~
money.cpp:50:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | while(p1 < left.size() || p2 < right.size()){
| ~~~^~~~~~~~~~~~~~
money.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | if(p1 == left.size()){
| ~~~^~~~~~~~~~~~~~
money.cpp:54:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | else if(p2 == right.size()){
| ~~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4188 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4188 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4188 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4184 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4188 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
