Submission #1034387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034387		istlemin	Fire (BOI24_fire)	C++17	100 / 100	591 ms	89528 KiB

Main

#include<bits/stdc++.h>

#pragma GCC optimize ("Ofast")

using namespace std;

#define rep(i,a,b) for(ll i = a; i<b;i++)
#define rrep(i,a,b) for(ll i = b-1; i>=a;i--)
#define trav(x,a) for(auto &x: a)
#define all(v) v.begin(),v.end()
#define sz(v) ll(v.size())

typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    ll n,m; cin>>n>>m;

    vl s(n);
    vl e(n);
    rep(i,0,n) cin>>s[i]>>e[i];

    vector<tuple<ll,ll,ll>> ev;
    rep(i,0,n){
        if(e[i]<s[i]){
            e[i]+=m;
        }
        ev.emplace_back(s[i],0,i);
        ev.emplace_back(e[i],1,i);
        ev.emplace_back(s[i]+m,0,i);
        ev.emplace_back(e[i]+m,1,i);
        ev.emplace_back(s[i]+m*2,0,i);
        ev.emplace_back(e[i]+m*2,1,i);
    }

    map<ll,ll> nextInterval;

    sort(all(ev));
    reverse(all(ev));
    set<pll> best;
    for(auto x: ev){
        auto [t,b,idx] = x;
        if(b==1){
            if(sz(best)){
                nextInterval[t] = max(nextInterval[t], prev(best.end())->first);
            }
            best.emplace(t,idx);
        } else {
            best.erase(make_pair(t+e[idx]-s[idx],idx));
        }
    }

    if(sz(nextInterval)==0){
        cout<<-1<<"\n";
        return 0;
    }

    // for(auto x: nextInterval){
    //     cout<<x.first<<": "<<x.second<<endl;
    // }

    deque<ll> q;
    q.push_front(nextInterval.begin()->first);
    ll topScore = 1e18;
    rep(i,0,10*n){
        // cout<<"q:"<<endl;
        // for(auto x:q){
        //     cout<<x<<" ";
        // }
        // cout<<endl;
        if(q.front()-q.back()>=m){
            topScore = min(topScore, sz(q)-1);
            q.pop_back();
        } else {
            if(nextInterval.find(q.front()) == nextInterval.end()){
                if(nextInterval.lower_bound(q.front())==nextInterval.end()) break;
                else {
                    ll t = nextInterval.lower_bound(q.front())->first;
                    q.clear();
                    q.push_front(t);
                }
            }
            q.push_front(nextInterval[q.front()]);
        }
    }
    if(topScore==1e18){
        cout<<-1<<"\n";
    } else 
        cout<<topScore<<"\n";

}

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