제출 #1140022

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140022		Ghulam_Junaid	Fire (BOI24_fire)	C++20	100 / 100	161 ms	31936 KiB

Main

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

const int N = 2e5 + 100, LG = 18;
int n, m, mx[N][LG], par[N][LG];
vector<pair<int, int>> vec;

int get_max(int l, int r){
    int lg = 31 - __builtin_clz(r - l + 1);
    if (vec[mx[l][lg]].second > vec[mx[r - (1 << lg) + 1][lg]].second)
        return mx[l][lg];
    return mx[r - (1 << lg) + 1][lg];
}

int main(){
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i ++){
        int l, r;
        cin >> l >> r;
        if (r < l) r += m;
        vec.push_back({l, r});
    }
    sort(vec.begin(), vec.end());

    for (int i = n - 1; i >= 0; i --){
        mx[i][0] = i;
        for (int j = 1; j < LG; j ++){
            mx[i][j] = mx[i][j - 1];
            if (i + (1 << (j - 1)) < n){
                if (vec[ mx[i + (1 << (j - 1))][j - 1] ].second > vec[mx[i][j]].second)
                mx[i][j] = mx[i + (1 << (j - 1))][j - 1];
            }
        }
    }

    for (int i = 0; i < n; i ++){
        auto [l, r] = vec[i];
        int j = upper_bound(vec.begin(), vec.end(), (pair<int,int>){r+1,-1}) - vec.begin();
        j--;
        par[i][0] = get_max(i, j);

        // cout << vec[i].first << " " << vec[i].second << " -- " << vec[par[i][0]].first << " " << vec[par[i][0]].second << endl;
    }

    for (int j = 1; j < LG; j ++)
        for (int i = 0; i < n; i ++)
            par[i][j] = par[par[i][j - 1]][j - 1];

    int ans = -1;
    for (int i = 0; i < n; i ++){
        int cur = i;
        int steps = 1;

        // cout << "----" << endl;
        // cout << vec[i].first << " " << vec[i].second << endl;
        for (int j = LG - 1; j >= 0; j --){
            if (par[cur][j] != cur and vec[par[cur][j]].second < vec[i].first + m){
                cur = par[cur][j];
                steps += 1 << j;
                // cout << vec[cur].first << " -" << j << "- " << vec[cur].second << endl;
            }
        }

        // cout << i << " " << steps << endl;
        if (vec[par[cur][0]].second >= vec[i].first + m)
            steps++;
        else
            steps = -1;

        if (steps == -1) continue;
        if (ans == -1 or ans > steps) ans = steps;
    }

    cout << ans << endl;
}

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