Submission #1080276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080276		oscar1f	Fire (BOI24_fire)	C++17	0 / 100	1 ms	348 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int MAX_INTER=200*1000+5,MAX_LOG=18,INFINI=1000*1000*1000;
int nbInter,tailleTour;
vector<pair<int,int>> listeInter;
int inter[MAX_INTER][2];
int proch[MAX_INTER];
int pere[MAX_INTER][MAX_LOG][2];
bool tourn[MAX_INTER];
multiset<pair<int,int>> enCours;

int tailleInter(int deb,int fin) {
    if (deb<fin) {
        return fin-deb;
    }
    else {
        return deb-fin;
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbInter>>tailleTour;
    for (int i=1;i<=nbInter;i++) {
        cin>>inter[i][0]>>inter[i][1];
        if (inter[i][0]<inter[i][1]) {
            listeInter.push_back({inter[i][0],-i});
            listeInter.push_back({inter[i][1],i});
            listeInter.push_back({inter[i][0]+tailleTour,-i});
            listeInter.push_back({inter[i][1]+tailleTour,i});
        }
        else {
            tourn[i]=true;
            listeInter.push_back({inter[i][0],-i});
            listeInter.push_back({inter[i][1]+tailleTour,i});
        }
    }
    multiset<pair<int,int>>::iterator it;
    sort(listeInter.begin(),listeInter.end());
    for (auto i:listeInter) {
        if (i.second<0) {
            i.second*=-1;
            if (tourn[i.second]) {
                enCours.insert({inter[i.second][1]+tailleTour,i.second});
            }
            else {
                enCours.insert({i.first-inter[i.second][0]+inter[i.second][1],i.second});
            }
        }
        else {
            if (tourn[i.second] or i.first<tailleTour) {
                it=enCours.end();
                it--;
                proch[i.second]=(*it).second;
                //cout<<i.second<<" "<<proch[i.second]<<endl;
            }
            it=enCours.lower_bound(i);
            enCours.erase(it);
        }
    }
    for (int i=1;i<=nbInter;i++) {
        pere[i][0][0]=proch[i];
        pere[i][0][1]=tailleInter(inter[i][1],inter[proch[i]][1]);
    }
    for (int j=1;j<MAX_LOG;j++) {
        for (int i=1;i<=nbInter;i++) {
            pere[i][j][0]=pere[pere[i][j-1][0]][j-1][0];
            pere[i][j][1]=pere[i][j-1][1]+pere[pere[i][j-1][0]][j-1][1];
        }
    }
    int pos,dejFait,nbUti,rep=INFINI;
    for (int i=1;i<=nbInter;i++) {
        pos=i;
        dejFait=tailleInter(inter[i][0],inter[i][1]);
        nbUti=1;
        for (int j=MAX_LOG-1;j>=0;j--) {
            if (dejFait+pere[pos][j][1]<tailleTour) {
                nbUti+=(1<<j);
                dejFait+=pere[pos][j][1];
                pos=pere[pos][j][0];
            }
        }
        nbUti++;
        dejFait+=pere[pos][0][1];
        if (dejFait>=tailleTour) {
            rep=min(rep,nbUti);
        }
    }
    if (rep==INFINI) {
        cout<<-1<<endl;
    }
    else {
        cout<<rep<<endl;
    }
    return 0;
}
 

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