oj.uz

Submission #895365

# Submission time Handle Problem Language Result Execution time Memory
895365 2023-12-29T19:37:36 Z Irate Money (IZhO17_money) C++14
45 / 100
 524 ms 262144 KB 
#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){
    if(indx == n + 1)return 0;
    if(dp[indx] != -1)return dp[indx];
    int res = rec(indx + 1) + 1, mn = v[indx], mx = v[indx];
    for(int i = indx + 1;i <= n;++i){
        mn = min(mn, v[i]);
        mx = max(mx, v[i]);
        if(v[i] < v[i - 1])break;
        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()){
      |                     ~~~^~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 1 ms 4184 KB Output is correct
3 Correct 1 ms 4184 KB Output is correct
4 Correct 1 ms 4188 KB Output is correct
5 Correct 1 ms 4224 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 4188 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 1 ms 4304 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 4184 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 1 ms 4184 KB Output is correct
3 Correct 1 ms 4184 KB Output is correct
4 Correct 1 ms 4188 KB Output is correct
5 Correct 1 ms 4224 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 4188 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 1 ms 4304 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 4184 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 4180 KB Output is correct
26 Correct 1 ms 4188 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 1 ms 4184 KB Output is correct
3 Correct 1 ms 4184 KB Output is correct
4 Correct 1 ms 4188 KB Output is correct
5 Correct 1 ms 4224 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 4188 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 1 ms 4304 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 4184 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 4180 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 1 ms 4188 KB Output is correct
30 Correct 1 ms 4188 KB Output is correct
31 Correct 1 ms 4188 KB Output is correct
32 Correct 2 ms 4308 KB Output is correct
33 Correct 1 ms 4444 KB Output is correct
34 Correct 1 ms 4444 KB Output is correct
35 Correct 1 ms 4444 KB Output is correct
36 Correct 1 ms 4312 KB Output is correct
37 Correct 1 ms 4444 KB Output is correct
38 Correct 1 ms 4444 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 1 ms 4184 KB Output is correct
3 Correct 1 ms 4184 KB Output is correct
4 Correct 1 ms 4188 KB Output is correct
5 Correct 1 ms 4224 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 4188 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 1 ms 4304 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 4184 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 4180 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 1 ms 4188 KB Output is correct
30 Correct 1 ms 4188 KB Output is correct
31 Correct 1 ms 4188 KB Output is correct
32 Correct 2 ms 4308 KB Output is correct
33 Correct 1 ms 4444 KB Output is correct
34 Correct 1 ms 4444 KB Output is correct
35 Correct 1 ms 4444 KB Output is correct
36 Correct 1 ms 4312 KB Output is correct
37 Correct 1 ms 4444 KB Output is correct
38 Correct 1 ms 4444 KB Output is correct
39 Correct 524 ms 191428 KB Output is correct
40 Runtime error 289 ms 262144 KB Execution killed with signal 9
41 Halted 0 ms 0 KB -