Submission #1080431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080431		Arturgo	Fire (BOI24_fire)	C++14	100 / 100	669 ms	113920 KiB

Main

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

const int DEBUT = -1;
const int FIN = 1;

struct Event {
    int pos, id, type, data;
};

bool operator < (const Event& a, const Event& b) {
    if(a.pos == b.pos) return a.type < b.type;
    return a.pos < b.pos;
}

int nbInters, nbCoords;

int nbProjs = 0;
vector<pair<int, int>> inters;
vector<Event> events;

void ajoute_inter(int deb, int fin) {
    inters.push_back({deb, fin});
    events.push_back({deb, nbProjs, DEBUT, fin});
    events.push_back({fin, nbProjs, FIN, -1});
    nbProjs++;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin >> nbInters >> nbCoords;

    for(int iInter = 0;iInter < nbInters;iInter++) {
        int deb, fin;
        cin >> deb >> fin;
        if(fin < deb) fin += nbCoords;
        ajoute_inter(deb, fin);
        ajoute_inter(deb + nbCoords, fin + nbCoords);
    }

    sort(events.begin(), events.end());

    vector<vector<int>> suivs(nbProjs, vector<int>(20, -1));

    pair<int, int> meilleureFin = {-1, -1}; // pos, id
    for(Event& ev : events) {
        if(ev.type == DEBUT) {
            if(ev.data > meilleureFin.first) {
                meilleureFin.first = ev.data;
                meilleureFin.second = ev.id;
            }
        } else if(ev.type == FIN) {
            if(meilleureFin.first > ev.pos) {
                suivs[ev.id][0] = meilleureFin.second;
            }
        }
    }

    for(int puis = 1;puis < 20;puis++) {
        for(int iProj = 0;iProj < nbProjs;iProj++) {
            if(suivs[iProj][puis - 1] != -1) {
                suivs[iProj][puis] = suivs[suivs[iProj][puis - 1]][puis - 1];
            }
        }
    }

    int minSelects = 1e9;
    for(int iProj = 0;iProj < nbProjs;iProj++) {
        int debActuel = inters[iProj].first;
        int nbSelects = 1;

        int iFin = iProj;
        for(int puis = 19;puis >= 0;puis--) {
            if(suivs[iFin][puis] == -1) continue;
            int finActuel = inters[suivs[iFin][puis]].second;
            if(finActuel < debActuel + nbCoords) {
                nbSelects += (1 << puis);
                iFin = suivs[iFin][puis];
            }
        }

        if(suivs[iFin][0] != -1) {
            minSelects = min(minSelects, nbSelects + 1);
        }
    }

    if(minSelects == 1e9) cout << -1 << endl;
    else cout << minSelects << endl;

    return 0;
}

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