Submission #1084642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084642		vjudge1	Fire (BOI24_fire)	C++17	100 / 100	770 ms	67880 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
using namespace std;
const int mxn=4e5+5;
struct mxtree{
    int t[2*mxn]{0};
    void upd(int i,int amt,int sz){
        i+=sz;t[i]=max(t[i],amt);
        for(i>>=1;i;i>>=1)t[i]=max(t[2*i],t[2*i+1]);
    }
    int qr(int l,int r,int sz,int res=0){
        for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
            if(l&1)res=max(res,t[l++]);
            if(r&1)res=max(res,t[--r]);
        }return res;
    }
}sg[20];int s[mxn],e[mxn];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m;cin>>n>>m;vector<int>v;
    for(int i=0;i<n;i++)cin>>s[i]>>e[i],v.pb(s[i]),v.pb(e[i]);
    sort(all(v));v.erase(unique(all(v)),v.end());int x=v.size();
    for(int i=0;i<n;i++)s[i]=lower_bound(all(v),s[i])-v.begin(),e[i]=lower_bound(all(v),e[i])-v.begin();
    for(int i=0;i<n;i++)if(s[i]<=e[i])sg[0].upd(s[i],e[i],x);
    for(int i=0;i<x;i++)sg[0].upd(i,sg[0].qr(0,i,x),x);
    for(int i=1;i<20;i++){
        for(int j=0;j<x;j++)sg[i].upd(j,sg[i-1].qr(j,sg[i-1].t[j+x]+1,x),x);
    }int ans=2e9;
    for(int i=0;i<n;i++){
        if(s[i]<=e[i])continue;
        int rs=0;int u=e[i];
        for(int j=19;j>=0;j--){
            if(sg[j].t[u+x]<s[i])rs+=(1<<j),u=sg[j].t[u+x];
        }
        if(sg[0].t[u+x]<s[i])continue;
        ans=min(ans,rs+2);
    }cout<<(ans==2e9?-1:ans);
}

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