Submission #1057060

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057060		underwaterkillerwhale	Fire (BOI24_fire)	C++17	48 / 100	85 ms	68016 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 1e6 + 7;
const int Mod = 1e9 + 7;
const int INF = 2e9 + 7;
const ll BASE = 137;
const int szBL = 320;

int m, n;
pii a[N];
int spt[N][25];
pii mx[N][25];

void solution () {
    cin >> n >> m;
    rep (i, 1, n) {
        cin >> a[i].fs >> a[i].se;
        if (a[i].se < a[i].fs) a[i].se = m + a[i].se;
    }
    sort (a + 1, a + 1 + n, [] (pii A, pii B) { return A.fs < B.fs || (A.fs == B.fs && A.se > B.se); });

    rep (i, 1, n) {
        mx[i][0] = MP(a[i].se, i);
    }
    for (int j = 1; (1 << j) <= n; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            mx[i][j] = max(mx[i][j - 1], mx[i + (1 << j - 1)][j - 1]);
    auto get = [] (int L, int R) -> pii {
        assert (L <= R);
        int K = 31 - __builtin_clz(R - L + 1);
        return max(mx[L][K], mx[R - (1 << K) + 1][K]);
    };
    rep (i, 1, n) {
        if (a[i].se >= m) spt[i][0] = i;
        else {
            int lf = i, rt = n;
            while (lf < rt) {
                int mid = lf + rt + 1 >> 1;
                if (a[mid].fs <= a[i].se) lf = mid;
                else rt = mid - 1;
            }
            spt[i][0] = get(i, lf).se;
//            cout << i << " "<<spt[i][0] <<"\n";
        }
    }
    rep (j, 1, 20)
    rep (i, 1, n)
        spt[i][j] = spt[spt[i][j - 1]][j - 1];
    int ans = INF;
    rep (i, 1, n) {
        int toreach = m + a[i].fs;
        int cur = i, res = 0;
        reb (j, 20, 0) {
            if (a[spt[cur][j]].se < toreach) {
                cur = spt[cur][j];
                res += (1 << j);
            }
        }
        ++res;
        cur = spt[cur][0];
//        cout << i<<" "<<cur <<" "<<toreach<<"\n";
        if (a[cur].se >= toreach) ans = min(ans, res + 1);
    }
    if (ans == INF) cout << -1 <<"\n";
    else  cout << ans <<"\n";

}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +2
2 + 8 * 2 - 9
6 2
1 5 2 3 1 1
1 2 3 3 2
4 5
6 6
*/

Compilation message (stderr)

Main.cpp: In function 'void solution()':
Main.cpp:45:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   45 |             mx[i][j] = max(mx[i][j - 1], mx[i + (1 << j - 1)][j - 1]);
      |                                                       ~~^~~
Main.cpp:56:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |                 int mid = lf + rt + 1 >> 1;
      |                           ~~~~~~~~^~~

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