| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 895356 | Irate | Money (IZhO17_money) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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, itr2 - itr1 + 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
*/
int rec(int indx){
int res = 1e9, mn = 1e9, mx = 0;
if(indx == n + 1)return 0;
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 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];
}
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;
}