Submission #1080554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080554		abouton	Fire (BOI24_fire)	C++17	100 / 100	462 ms	106492 KiB

Main

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

struct ev
{
    int pos, type, id, fin;
    bool operator<(const ev &autre) const
    {
        if (pos == autre.pos) return type < autre.type;
        return pos < autre.pos;
    }
};
const int LOG = 20, PUIS = (1<<20);
const int DEB = -1, FIN = 1;

int N, mod;
int nbI;
int suivs[4*(int)1e5 + 42][LOG];
vector<ev> tri;
vector<pair<int,int>> inters;

void aj(int d, int f)
{
    inters.push_back({d, f});
    tri.push_back({d, DEB, nbI, f});
    tri.push_back({f, FIN, nbI, -1});
    nbI++;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin >> N >> mod;

    for (int i = 0; i < N; i ++)
    {
        int d, f;
        cin >> d >> f;
        if (f<d) f += mod;
        aj(d, f);
        aj(d+mod,f+mod);
    }
    for (int i = 0; i < nbI; i ++)
    {
        for (int j = 0; j < 20;j ++)
        {
            suivs[i][j] = -1;
        }
    }
    sort(tri.begin(), tri.end());
    int ind=-1, maxi=-1;
    for (auto i : tri)
    {
        if (i.type == DEB)
        {
            if (i.fin > maxi)
            {
                maxi = i.fin;
                ind = i.id;
            }
        }
        if (i.type == FIN)
        {
            if (maxi > i.pos) suivs[i.id][0] = ind;
        }
    }
    
    for (int l = 1; l < 20; l ++)
    {
        for (int i = 0; i < nbI; i ++)
        {
            if (suivs[i][l-1] != -1) suivs[i][l] = suivs[suivs[i][l-1]][l-1];
        }
    }

    int mini = 1e9;
    for (int i = 0; i < nbI; i ++)
    {
        int curPos = i;
        int deb = inters[i].first;
        int nbS = 1;
        for (int av = 19; av >= 0; av --)
        {
            if (suivs[curPos][av] == -1) continue;
            if (inters[suivs[curPos][av]].second < deb+mod) {curPos = suivs[curPos][av];nbS += (1<<av);}
            //if (i == 2){cout <<av<<' ' <<curPos<<inters[suivs[curPos][av]].second << ' '<<nbS <<'\n';}
        }
        if (suivs[curPos][0] != -1) mini = min(mini, nbS+1);
    }
    if (mini == (int)1e9) mini = -1;

    cout << mini << '\n';
    //for (int i = 0; i < nbI; i ++) cout << suivs[i][2] << ' ';
}

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