Submission #1140046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140046		Sir_Ahmed_Imran	Fire (BOI24_fire)	C++20	100 / 100	373 ms	45828 KiB

Main

                //    01001100 01001111 01010100 01000001    \\
                //                                           \\
                //                ╦  ╔═╗╔╦╗╔═╗               \\
                //                ║  ║ ║ ║ ╠═╣               \\
                //                ╩═╝╚═╝ ╩ ╩ ╩               \\
                //                                           \\
                //    01001100 01001111 01010100 01000001    \\

#include <bits/stdc++.h>
using namespace std;

#define N 500001
#define M 20
#define nl '\n'
#define ff first
#define ss second
#define add insert
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

int n, m;
int mx[N][M];
vector<pii> v, x, y;

int get(int i, int j){
    int ans = 0;
    i++;
    while(i){
        ans = max(ans, mx[i][j]);
        i -= i & - i;
    }
    return ans;
}

void update(int i, int j, int k){
    i ++;
    while(i <= m){
        if(j) mx[i][j] = max(mx[i][j], mx[i][j - 1]);
        mx[i][j] = max(mx[i][j], k);
        i += i & - i;
    }
}

int steps(int l, int r){
    int o, ans;
    ans = 0;
    for(int i = M - 1; i >= 0; i--){
        o = get(l, i);
        if(o >= r) continue;
        l = o, ans += 1 << i;
    }
    return ans + 1;
}

void compress(){
    vector<int> u {0};
    unordered_map<int, int> c;
    for (auto & [i, j] : v){
        u.append(i);
        u.append(j);
    }
    sort(all(u));
    int cnt = 1;
    c[0] = 0;
    for (int i = 1; i < u.size(); i++){
        if(u[i] == u[i - 1])
            continue;
        c[u[i]] = cnt;
        cnt++;
    }
    m = cnt;
    for (auto & [i, j] : v)
        i = c[i], j = c[j];
}

bool possible(){
    int r = 0;
    for(auto & [i, j] : x){
        if(i > r) 
            break;
        r = max(r, j);
    }
    return r == m;
}

void solve(){
    int p, q;
    cin >> n >> m;
    for (int i = 0; i < n; i++){
        cin >> p >> q;
        v.append({p, q}); 
    }
    compress();
    for (auto & [i, j] : v){
        if(i > j){
            x.append({0, j});
            x.append({i, m});
            y.append({i, j});
        }
        else x.append({i, j});
    }
    sort(all(x));
    if(!possible()){
        cout << "-1";
        return;
    }
//    for (auto & [i, j] : x)
//        cout << i << ' ' << j <<nl;
    reverse(all(x));
    for (auto & [i, j] : x){
        update(i, 0, j);
        for(int k = 0; k < M-1; k++)
            update(i, k + 1, get(get(i, k), k));
    }
    int ans = steps(0, m);
    for (auto & [r, l] : y){
        ans = min(ans, steps(l, r) + 1);
//        cout << l << ' ' << r << ' ' << steps(l, r) << nl;
    }
    cout << ans;
}

int terminator(){
    L0TA;
    solve();
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 17 / 17
• Subtask 3: 9 / 9
• Subtask 4: 13 / 13
• Subtask 5: 21 / 21
• Subtask 6: 26 / 26