Submission #1274990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274990		Bui_Quoc_Cuong	Fire (BOI24_fire)	C++20	100 / 100	108 ms	44340 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
template<class T>
    bool minimize(T &a, const T &b) {
        if (a > b) return a = b, true;
        return false;
    }
template<class T>
    bool maximize(T &a, const T &b) {
        if (a < b) return a = b, true;
        return false;
    }
const int N = 5e5 + 5;

int n, cir;
struct Lines {
    int st, ed;
};
Lines line[N];

void init () {
    cin >> n >> cir;
    for (int i = 1; i <= n; i++) {
        cin >> line[i].st >> line[i].ed;
        line[i].st++; line[i].ed++;
    }
    for (int i = 1; i <= n; i++) if (line[i].st > line[i].ed) line[i].ed+= cir;
}

Lines b[N];
int rmq[N][22];

void process () {
    sort(line + 1, line + 1 + n, [&] (Lines u, Lines v) {
        if (u.st == v.st) return u.ed < v.ed;
        return u.st < v.st;
    });

    int m = 0;
    vector <pair <int, int>> seg;
    for (int i = 1; i <= n; i++) {
        if (!seg.empty() && seg.back().second >= line[i].ed) continue;
        seg.push_back(make_pair(line[i].st, line[i].ed));
    }

    for (int i = 0; i < seg.size(); i++) b[i + 1] = {seg[i].first, seg[i].second};
    m = seg.size();

    int j = 1;
    for (int i = 1; i <= m; i++) {
        while (j <= m && b[j].st <= b[i].ed) j++;
        rmq[i][0] = j - 1;
    }
    for (int j = 1; (1 << j) <= m; j++) {
        for (int i = 1; i <= m; i++) {
            rmq[i][j] = rmq[rmq[i][j - 1]][j - 1];
        }
    }

    auto ask = [&] (int u, int R) {
        int res = 1;

//        cout << rmq[u][0] << "\n";

        for (int s = 18; s >= 0; s--) {
            int nxt = rmq[u][s];
            if (b[nxt].ed < R && b[nxt].ed > 0) {
//                cout << u << " " << nxt << "\n";
                u = nxt;
                res+= (1 << s);
            }
        }

        for (int s = 0; s <= 18; s++) if (b[rmq[u][s]].ed >= R) {
            return res + (1 << s);
        }

        return (int) 2e9;
    };

    int ans = 2e9;

    for (int i = 1; i <= m; i++) {
       /// cout << b[i].st << " " << b[i].ed << "\n";
    }

    for (int i = 1; i <= m; i++) {
        int R = b[i].st + cir;
        ///cout << i << " " << b[i].st << " " << R << " " << ask(i, R) << "\n";
        ans = min(ans, ask(i, R));
    }

    if (ans == 2e9) cout << - 1;
    else cout << ans;
}

signed main () {
    ios_base :: sync_with_stdio(0); cin.tie(0);
    #define taskname "cungtroncc"
    if (fopen(taskname".inp", "r")) {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    init();
    process();
    return 0;
}
/*
4 10
1 3
3 7
2 4
6 2
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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