Submission #1267177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267177		Nika533	Fire (BOI24_fire)	C++20	0 / 100	2091 ms	3512 KiB

Main

#include <bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
using namespace std;

const int N=2e5+5;
int n,m,l[N],r[N];

int main() {
    cin>>n>>m;
    vector<pii> v;
    for (int i=1; i<=n; i++) {
        cin>>l[i]>>r[i]; v.push_back({l[i],r[i]});
    }
    sort(all(v));
    for (int i=1; i<=n; i++) {
        l[i]=v[i-1].f; r[i]=v[i-1].s;
    }
    int cnt=1e9;
    for (int i=1; i<=n; i++) {
        int last=r[i],mx=0;
        int cnt2=1;
        if (last<l[i]) last+=m;
        for (int j=i; j<=n; j++) {
            int L=l[j],R=r[j];
            if (L>R) R+=m;
            if (L>last) {
                if (L>mx) {
                    cout<<-1<<endl;
                    return 0;
                }
                // cout<<i<<" "<<j<<endl;
                cnt2++; j--; last=mx; mx=0; continue;
            }
            mx=max(mx,R);
        }
        for (int j=1; j<=i; j++) {
            int L=l[j],R=r[j];
            L+=m; R+=m;
            if (L>last) {
                if (L>mx) {
                    cout<<-1<<endl;
                    return 0;
                }
                // cout<<i<<" "<<j<<endl;
                cnt2++; j--; last=mx; mx=0; continue;
            }
            mx=max(mx,R);
        }
        if (mx-m>=l[i]) cnt=min(cnt,cnt2);
        // cout<<"ANS "<<i<<" "<<cnt2<<endl;
    }
    cout<<cnt<<endl;
}

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