제출 #1141667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141667		SyedSohaib_123	Fire (BOI24_fire)	C++20	14 / 100	2096 ms	964 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define append push_back
#define int long long

const int N=2e5+10,LG=17;
int mod=998244353;

int tree[N<<3];

void upd(int l,int r,int s,int a,int b,int x){
    if(r<a or l>b) return;
    if(a<=l and r<=b){
        tree[s]=max(tree[s],x);
        return;
    }
    int m=(l+r)>>1;
    upd(l,m,s*2,a,b,x);
    upd(m+1,r,s*2+1,a,b,x);
    tree[s]=max(tree[s*2],tree[s*2+1]);
}

int get(int l,int r,int s,int a,int b){
    if(r<a or l>b) return 0;
    if(a<=l and r<=b) return tree[s];
    int m=(l+r)>>1;
    return max(get(l,m,s*2,a,b),get(m+1,r,s*2+1,a,b));
}

void solve(int tst){
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>>v={{0,0}};
    for(int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        v.append({a,b});
    }
    vector<pair<int,int>>t;
    for(int i=1;i<=n;i++){
        t.append({v[i].first,i});
        t.append({v[i].second,i+n});
    }
    t.append({0,0});
    t.append({m,1e18});
    sort(t.begin(),t.end());
    int cnt=1;
    for(int i=1;i<t.size();i++){
        if(t[i].first!=t[i-1].first) cnt++;
        int j=t[i].second;
        if(j and j<=n){
            v[j].first=cnt;
        }
        if(j>n and j!=1e18){
            v[j-n].second=cnt;
        }
    }
    sort(v.begin(),v.end());
    int ans=1e18;
    for(int i=1;i<=n;i++){
        upd(1,cnt,1,v[i].first,v[i].first,v[i].second+m*(v[i].second<v[i].first));
    }
    for(int X=1;X<=n;X++){
        int r=v[X].second;
        int x=1,p=0,q=0;
        while(1){
            int nxt=1e18;
            if(v[X].first<r) nxt=get(1,cnt,1,v[X].first,r);
            else nxt=min(get(1,cnt,1,v[X].first,cnt),get(1,cnt,1,1,r));
            if(nxt==r) break;
            r=nxt;
            if(r>m){
                r-=m;
                q=m;
            }
            x++;
            if(r+q>=v[X].first+m and v[X].first<v[X].second) {p=1;break;}
            if(r+q>=v[X].first and v[X].first>v[X].second) {p=1;break;}
        }
        if(p) ans=min(ans,x);
    }
    if(ans==1e18) ans=-1;
    cout<<ans<<endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; i++) {
        solve(i);
    }
}

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