Submission #1084693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084693		tvladm2009	Fire (BOI24_fire)	C++17	100 / 100	1411 ms	415916 KiB

Main

#include <bits/stdc++.h>
 
 
using namespace std;
 
 
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


const int L = 20;


ll n, m;
vector<ll> s, e;


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n >> m;
    s.resize(2 * n + 1);
    e.resize(2 * n + 1);
    map<ll, pair<ll, ll>> f;
    for (int i = 1; i <= n; i += 1) {
        cin >> s[i] >> e[i];
        if (s[i] > e[i]) {
            e[i] += m;
        }
        f[s[i]] = max(f[s[i]], {e[i], i});
        f[e[i]] = max(f[e[i]], {-1, -1});
    }
    for (int i = n + 1; i <= 2 * n; i += 1) {
        s[i] = s[i - n] + m;
        e[i] = e[i - n] + m;
        f[s[i]] = max(f[s[i]], {e[i], i});
        f[e[i]] = max(f[e[i]], {-1, -1});
    }
    vector<pair<ll, pair<ll, ll>>> vals;
    for (auto it : f) {
        vals.push_back({it.first, it.second});
    }
    map<ll, ll> where;
    vector<vector<pair<ll, ll>>> rmq(L, vector<pair<ll, ll>>(vals.size() + 1));
    for (int i = 1; i <= vals.size(); i += 1) {
        rmq[0][i] = vals[i - 1].second;
        where[vals[i - 1].first] = i;
    }
    for (int h = 1; h < L; h += 1) {
        for (int i = 1; i + (1 << h) - 1 <= vals.size(); i += 1) {
            rmq[h][i] = max(rmq[h - 1][i], rmq[h - 1][i + (1 << (h - 1))]);
        }
    }
    vector<int> lg(vals.size() + 1);
    for (int i = 2; i <= vals.size(); i += 1) {
        lg[i] = lg[i / 2] + 1;
    }
    auto query = [&](int l, int r) {
        l = where[l];
        r = where[r];
        int h = lg[r - l + 1];
        return max(rmq[h][l], rmq[h][r - (1 << h) + 1]);
    };
    vector<vector<int>> nxt(L, vector<int>(2 * n + 1));
    for (int i = 1; i <= 2 * n; i += 1) {
        nxt[0][i] = query(s[i], e[i]).second;
    }
    for (int h = 1; h < L; h += 1) {
        for (int i = 1; i <= 2 * n; i += 1) {
            nxt[h][i] = nxt[h - 1][nxt[h - 1][i]];
        }
    }
    int ans = n + 1;
    for (int i = 1; i <= n; i += 1) {
        int cur = 1;
        int x = i;
        for (int h = L - 1; h >= 0; h -= 1) {
            if (e[nxt[h][x]] < s[i] + m) {
                cur += (1 << h);
                x = nxt[h][x];
            }
        }
        x = nxt[0][x];
        cur += 1;
        if (e[x] >= s[i] + m) {
            ans = min(ans, cur);
        }
    }
    if (ans == n + 1) {
        cout << -1 << "\n";
        return 0;
    }
    cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 1; i <= vals.size(); i += 1) {
      |                     ~~^~~~~~~~~~~~~~
Main.cpp:55:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int i = 1; i + (1 << h) - 1 <= vals.size(); i += 1) {
      |                         ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
Main.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int i = 2; i <= vals.size(); i += 1) {
      |                     ~~^~~~~~~~~~~~~~

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