oj.uz

Submission #1080284

# Submission time Handle Problem Language Result Execution time Memory
1080284 2024-08-29T08:38:00 Z oscar1f Fire (BOI24_fire) C++17
0 / 100
 1 ms 6492 KB 
#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 tailleTour-(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]);
        //cout<<dejFait<<" ";
        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];
        //cout<<i<<" "<<nbUti<<endl;
        if (dejFait>=tailleTour) {
            rep=min(rep,nbUti);
        }
    }
    if (rep==INFINI) {
        cout<<-1<<endl;
    }
    else {
        cout<<rep<<endl;
    }
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -