Submission #1116546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116546		Pekiban	Fire (BOI24_fire)	C++17	100 / 100	412 ms	74160 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
#define pb push_back
 
const int N = 4e5+5, LOG = 18;
vector<long long> B;
map<int, int> go, f;
int up[N][LOG];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        int s, e;
        cin >> s >> e;
        // e++;
        if (s >= e)  e += m;
        B.pb(s); B.pb(e);
        go[s] = max(go[s], e);
    }
    sort(B.begin(), B.end());
    B.erase(unique(B.begin(), B.end()), B.end());
    for (int i = 0; i < B.size(); ++i)  f[B[i]] = i;
    for (int i = 0; i < B.size(); ++i)  up[i][0] = max({up[i][0], f[go[B[i]]], i});
    for (int i = 1; i < B.size(); ++i)  up[i][0] = max(up[i-1][0], up[i][0]);
    for (int j = 1; j < LOG; ++j) {
        for (int i = 0; i < B.size(); ++i)  up[i][j] = up[up[i][j-1]][j-1];
    }
    int ans = 1e9;
    for (int i = 0; i < B.size(); ++i) {
        int x = i, c = 0;
        for (int j = LOG-1; j >= 0; --j) {
            if (B[up[x][j]] <= B[i] + m - 1) {
                x = up[x][j], c += (1 << j);
            }
        }
        if (B[up[x][0]] >= B[i] + m)    ans = min(ans, c + 1);
    }
    cout << (ans > n ? -1 : ans) << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (int i = 0; i < B.size(); ++i)  f[B[i]] = i;
      |                     ~~^~~~~~~~~~
Main.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i = 0; i < B.size(); ++i)  up[i][0] = max({up[i][0], f[go[B[i]]], i});
      |                     ~~^~~~~~~~~~
Main.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i = 1; i < B.size(); ++i)  up[i][0] = max(up[i-1][0], up[i][0]);
      |                     ~~^~~~~~~~~~
Main.cpp:29:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (int i = 0; i < B.size(); ++i)  up[i][j] = up[up[i][j-1]][j-1];
      |                         ~~^~~~~~~~~~
Main.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < B.size(); ++i) {
      |                     ~~^~~~~~~~~~

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