oj.uz

Submission #1052477

# Submission time Handle Problem Language Result Execution time Memory
1052477 2024-08-10T14:58:28 Z Phuoc Money (IZhO17_money) C++14
100 / 100
 280 ms 30744 KB 
#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set> 

using namespace std;
 
#define ll long long
#define pb push_back
#define el '\n'
#define mpair make_pair
#define MASK(i) (1LL << (i))
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define fi first
#define se second
#define all(v) v.begin(), v.end()
 
/* Author: Pham Gia Phuoc */
 
const ll MOD = (ll)(1e9) + 7LL;
 
template <class T1, class T2>
    void add(T1 &a, T2 b){
        a += b;
        if(a >= MOD) a -= MOD;
    }
 
template <class T1, class T2>
    void sub(T1 &a, T2 b){
        a -= b;
        if(a < 0) a += MOD;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if(a > b){a = b; return true;} return false;
    }
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if(a < b){a = b; return true;} return false;
    }
 
/** END OF TEMPLATE. DRINK A CUP OF COFFEE BEFORE READING MY CODE **/
 
const int MAX = (int)(1e6) + 10;
const ll INF = (ll) 1e18 + 67LL;
const int oo = (int)(1e9 + 7);
const int NUM_BIT = 62;

#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)

int n, a[MAX];

void init(){
    cin >> n;
    FOR(i, 1, n) cin >> a[i];
}

namespace subtask1{
    bool check(){
        return n <= 1e3;
    }

    const int MAXN = (int)(1e3) + 10;
    vector <int> cur[MAXN];
    int dp[MAXN];    

    void solve(){
        FOR(i, 1, n){
            FOR(j, 1, i){
                cur[i].push_back(a[j]);
            }   
            sort(cur[i].begin(), cur[i].end());
            cur[i].resize(unique(cur[i].begin(), cur[i].end()) - cur[i].begin());
        }
    
        dp[0] = 0;
        FOR(i, 1, n){
            dp[i] = dp[i - 1] + 1;
            FORD(j, i - 1, 1){
                if(a[j] > a[j + 1]) break;
                if(a[j] == a[i]){
                    minimize(dp[i], dp[j - 1] + 1);
                    continue;
                }
                int cnt = upper_bound(cur[j - 1].begin(), cur[j - 1].end(), a[i] - 1) - lower_bound(cur[j - 1].begin(), cur[j - 1].end(), a[j] + 1);
                if(cnt != 0) continue;
                minimize(dp[i], dp[j - 1] + 1);
            }
        }
        cout << dp[n];
    }
}

namespace subtask2{
    bool check(){
        return n <= 1e6;
    }

    struct styn{
        vector <int> IT;
        int n;
        styn(int _n = 0){
            n = _n;
            IT.resize(n * 4 + 10, 0);
        }

        void Update(int p){
            int i = 1, l = 1, r = n;
            while(l < r){
                int m = (l + r) >> 1;
                if(p > m){l = m + 1; i = i * 2 + 1;}
                else{r = m; i = i * 2;}
            }
            IT[i]++;
            while(i > 1){
                i >>= 1;
                IT[i] = IT[i * 2] + IT[i * 2 + 1];
            }
        }

        int Get(int i, int l, int r, int u, int v){
            if(l > v || r < u) return 0;
            if(u <= l && r <= v) return IT[i];
            int m = (l + r) >> 1;
            return Get(i * 2, l, m, u, v) + Get(i * 2 + 1, m + 1, r, u, v);
        }
    };

    int dp[MAX];

    void solve(){
        int ma = a[max_element(a + 1, a + n + 1) - a];
        styn tree(ma);
        memset(dp, 0x3f, sizeof dp);
        dp[0] = 0;
        for(int i = 1, j = 1; i <= n; i++){
            while(j < i && a[i] < a[i - 1]) tree.Update(a[j++]);
            while(j < i && tree.Get(1, 1, ma, a[j] + 1, a[i] - 1) != 0) tree.Update(a[j++]);
            minimize(dp[i], dp[j - 1] + 1);
        }
        cout << dp[n];
    }
}

void solve(){  
    // if(subtask1::check()){subtask1::solve(); return;}
    if(subtask2::check()){subtask2::solve(); return;}
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define test "test"
    // freopen(test".inp", "r", stdin);
    // freopen(test".out", "w", stdout);
    srand(time(0));
    int t = 1;
    while(t--){
        init();
        solve();
    }
    return 0;
}
 
 
 
/*** ROAD TO VOI 2025 ***/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 0 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 0 ms 4700 KB Output is correct
7 Correct 3 ms 16220 KB Output is correct
8 Correct 3 ms 20100 KB Output is correct
9 Correct 2 ms 13660 KB Output is correct
10 Correct 2 ms 13660 KB Output is correct
11 Correct 3 ms 17756 KB Output is correct
12 Correct 3 ms 15708 KB Output is correct
13 Correct 3 ms 17244 KB Output is correct
14 Correct 2 ms 13484 KB Output is correct
15 Correct 3 ms 20112 KB Output is correct
16 Correct 3 ms 18560 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 0 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 0 ms 4700 KB Output is correct
7 Correct 3 ms 16220 KB Output is correct
8 Correct 3 ms 20100 KB Output is correct
9 Correct 2 ms 13660 KB Output is correct
10 Correct 2 ms 13660 KB Output is correct
11 Correct 3 ms 17756 KB Output is correct
12 Correct 3 ms 15708 KB Output is correct
13 Correct 3 ms 17244 KB Output is correct
14 Correct 2 ms 13484 KB Output is correct
15 Correct 3 ms 20112 KB Output is correct
16 Correct 3 ms 18560 KB Output is correct
17 Correct 5 ms 19548 KB Output is correct
18 Correct 3 ms 17244 KB Output is correct
19 Correct 2 ms 17500 KB Output is correct
20 Correct 3 ms 20060 KB Output is correct
21 Correct 3 ms 15196 KB Output is correct
22 Correct 3 ms 19036 KB Output is correct
23 Correct 3 ms 17244 KB Output is correct
24 Correct 3 ms 16220 KB Output is correct
25 Correct 3 ms 18012 KB Output is correct
26 Correct 3 ms 19804 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 0 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 0 ms 4700 KB Output is correct
7 Correct 3 ms 16220 KB Output is correct
8 Correct 3 ms 20100 KB Output is correct
9 Correct 2 ms 13660 KB Output is correct
10 Correct 2 ms 13660 KB Output is correct
11 Correct 3 ms 17756 KB Output is correct
12 Correct 3 ms 15708 KB Output is correct
13 Correct 3 ms 17244 KB Output is correct
14 Correct 2 ms 13484 KB Output is correct
15 Correct 3 ms 20112 KB Output is correct
16 Correct 3 ms 18560 KB Output is correct
17 Correct 5 ms 19548 KB Output is correct
18 Correct 3 ms 17244 KB Output is correct
19 Correct 2 ms 17500 KB Output is correct
20 Correct 3 ms 20060 KB Output is correct
21 Correct 3 ms 15196 KB Output is correct
22 Correct 3 ms 19036 KB Output is correct
23 Correct 3 ms 17244 KB Output is correct
24 Correct 3 ms 16220 KB Output is correct
25 Correct 3 ms 18012 KB Output is correct
26 Correct 3 ms 19804 KB Output is correct
27 Correct 1 ms 4700 KB Output is correct
28 Correct 0 ms 4700 KB Output is correct
29 Correct 1 ms 4700 KB Output is correct
30 Correct 1 ms 4700 KB Output is correct
31 Correct 1 ms 4700 KB Output is correct
32 Correct 4 ms 18640 KB Output is correct
33 Correct 3 ms 15196 KB Output is correct
34 Correct 3 ms 19804 KB Output is correct
35 Correct 2 ms 12124 KB Output is correct
36 Correct 4 ms 17244 KB Output is correct
37 Correct 3 ms 20060 KB Output is correct
38 Correct 3 ms 20316 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 0 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 0 ms 4700 KB Output is correct
7 Correct 3 ms 16220 KB Output is correct
8 Correct 3 ms 20100 KB Output is correct
9 Correct 2 ms 13660 KB Output is correct
10 Correct 2 ms 13660 KB Output is correct
11 Correct 3 ms 17756 KB Output is correct
12 Correct 3 ms 15708 KB Output is correct
13 Correct 3 ms 17244 KB Output is correct
14 Correct 2 ms 13484 KB Output is correct
15 Correct 3 ms 20112 KB Output is correct
16 Correct 3 ms 18560 KB Output is correct
17 Correct 5 ms 19548 KB Output is correct
18 Correct 3 ms 17244 KB Output is correct
19 Correct 2 ms 17500 KB Output is correct
20 Correct 3 ms 20060 KB Output is correct
21 Correct 3 ms 15196 KB Output is correct
22 Correct 3 ms 19036 KB Output is correct
23 Correct 3 ms 17244 KB Output is correct
24 Correct 3 ms 16220 KB Output is correct
25 Correct 3 ms 18012 KB Output is correct
26 Correct 3 ms 19804 KB Output is correct
27 Correct 1 ms 4700 KB Output is correct
28 Correct 0 ms 4700 KB Output is correct
29 Correct 1 ms 4700 KB Output is correct
30 Correct 1 ms 4700 KB Output is correct
31 Correct 1 ms 4700 KB Output is correct
32 Correct 4 ms 18640 KB Output is correct
33 Correct 3 ms 15196 KB Output is correct
34 Correct 3 ms 19804 KB Output is correct
35 Correct 2 ms 12124 KB Output is correct
36 Correct 4 ms 17244 KB Output is correct
37 Correct 3 ms 20060 KB Output is correct
38 Correct 3 ms 20316 KB Output is correct
39 Correct 78 ms 22964 KB Output is correct
40 Correct 118 ms 26824 KB Output is correct
41 Correct 63 ms 21848 KB Output is correct
42 Correct 60 ms 23860 KB Output is correct
43 Correct 36 ms 22364 KB Output is correct
44 Correct 142 ms 29012 KB Output is correct
45 Correct 142 ms 28728 KB Output is correct
46 Correct 150 ms 30024 KB Output is correct
47 Correct 150 ms 29776 KB Output is correct
48 Correct 167 ms 27732 KB Output is correct
49 Correct 203 ms 30544 KB Output is correct
50 Correct 204 ms 30744 KB Output is correct
51 Correct 194 ms 30544 KB Output is correct
52 Correct 196 ms 30744 KB Output is correct
53 Correct 196 ms 30548 KB Output is correct
54 Correct 201 ms 30544 KB Output is correct
55 Correct 268 ms 30544 KB Output is correct
56 Correct 245 ms 30524 KB Output is correct
57 Correct 248 ms 30532 KB Output is correct
58 Correct 248 ms 30660 KB Output is correct
59 Correct 249 ms 30548 KB Output is correct
60 Correct 280 ms 30652 KB Output is correct
61 Correct 244 ms 30552 KB Output is correct
62 Correct 247 ms 30664 KB Output is correct