Submission #1267199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267199		Nika533	Fire (BOI24_fire)	C++20	100 / 100	145 ms	41384 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define pb push_back
#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],t[N][20];

main() {
    cin>>n>>m;
    vector<pii> v,v2;
    for (int i=1; i<=n; i++) {
        cin>>l[i]>>r[i];
        v.push_back({l[i],-r[i]});
    }
    sort(all(v)); sort(all(v2));
    for (int i=1; i<=n; i++) {
        l[i]=v[i-1].f; r[i]=-v[i-1].s;
        if (l[i]>r[i]) v2.pb({r[i],i});
    }

    pii mx={-1,-1};
    int last=1;
    for (int i=1; i<=n; i++) {
        if (l[i]>r[i]) continue;
        while (l[last]>r[last]) last++;
        if (r[last]<l[i]) {
            while (l[last]>r[last]) last++;
            t[last][0]=mx.s;
            // cout<<"LAST "<<last<<" "<<mx.s<<endl;
            last++; i--;
            continue;
        }
        mx=max(mx,{r[i],i});
    }
    while (last<=n) {
        t[last][0]=mx.s; last++;
    }
    for (int j=1; j<20; j++) {
        for (int i=1; i<=n; i++) {
            if (l[i]>r[i]) continue;
            t[i][j]=t[t[i][j-1]][j-1];
        }
    }

    int cnt=1e9,big=1e9;
    mx={-1,-1};
    last=0;
    for (auto A:v2) {
        int i=A.s;
        // cout<<"I "<<i<<endl;
        while (last+1<=n && l[last+1]<=r[i]) {
            last++;
            if (l[last]>r[last]) continue;
            mx=max(mx,{r[last],last});
        }
        if (mx.s==-1) continue;
        int ind=mx.s;
        if (r[t[ind][19]]<l[i]) continue;
        int num=3;
        if (r[ind]>=l[i]) num--;
        for (int j=19; j>=0; j--) {
            // cout<<i<<" "<<j<<" "<<t[ind][j]<<" "<<ind<<endl;
            if (r[t[ind][j]]<l[i]) {
                ind=t[ind][j];
                num+=(1<<j);
            }
        }
        cnt=min(cnt,num);
    }
    if (cnt==big) cnt=-1;
    cout<<cnt<<endl;
}

Compilation message (stderr)

Main.cpp:14:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   14 | main() {
      | ^~~~

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