Submission #1052477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052477		Phuoc	Money (IZhO17_money)	C++14	100 / 100	280 ms	30744 KiB

money

#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 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55