Submission #1024260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024260		serifefedartar	Fire (BOI24_fire)	C++17	100 / 100	597 ms	95428 KiB

Main

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

#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define LOGN 20
const ll MOD = 1e9 + 7;
const ll MAXN = 8e5 + 100;

ll N, M;
int s[MAXN], e[MAXN], sg[4*MAXN], lazy[4*MAXN];
int up[LOGN][MAXN], mn = 1e7;
vector<int> cc;
void push(int k, int a, int b) {
    if (lazy[k] != -1) {
        sg[k] = max(sg[k], lazy[k]);
        if (a != b) {
            lazy[2*k] = max(lazy[2*k], lazy[k]);
            lazy[2*k+1] = max(lazy[2*k+1], lazy[k]);
        }
        lazy[k] = -1;
    }
}

void init(int k, int a, int b) {
    if (a == b) {
        sg[k] = a;
        return ;
    }
    init(2*k, a, (a+b)/2);
    init(2*k+1, (a+b)/2+1, b);
    sg[k] = max(sg[2*k], sg[2*k+1]);
}

void update(int k, int a, int b, int q_l, int q_r, int val) {
    push(k, a, b);
    if (b < q_l || a > q_r)
        return ;
    if (q_l <= a && b <= q_r) {
        lazy[k] = val;
        push(k, a, b);
        return ;
    }
    update(2*k, a, (a+b)/2, q_l, q_r, val);
    update(2*k+1, (a+b)/2+1, b, q_l, q_r, val);
    sg[k] = max(sg[2*k], sg[2*k+1]);
}

int query(int k, int a, int b, int plc) {
    push(k, a, b);
    if (b < plc || a > plc)
        return 0;
    if (a == b)
        return sg[k];
    return max(query(2*k, a, (a+b)/2, plc),
                query(2*k+1, (a+b)/2+1, b, plc));
}

void try_i(int node) {
    int now = node;
    int x = 0;
    for (int i = LOGN-1; i >= 0; i--) {
        int y = up[i][now];
        if (cc[y-1] < cc[node-1] + M) {
            now = y;
            x += (1<<i);
        }
    }

    int y = up[0][now];
    if (cc[y-1] >= cc[node-1] + M)
        mn = min(mn, x + 1);
}

int main() {
    fast
    cin >> N >> M;

    for (int i = 1; i <= N; i++) {
        cin >> s[i] >> e[i];
        cc.push_back(s[i]);
        cc.push_back(e[i]);
        cc.push_back(s[i] + M);
        cc.push_back(e[i] + M);
    }
    sort(cc.begin(), cc.end());
    cc.erase(unique(cc.begin(), cc.end()), cc.end());
    int n = cc.size();
    init(1, 0, n);

    for (int i = 1; i <= N; i++) {
        if (s[i] <= e[i]) {
            int x1 = upper_bound(cc.begin(), cc.end(), s[i]) - cc.begin();
            int x2 = upper_bound(cc.begin(), cc.end(), e[i]) - cc.begin();
            int y1 = upper_bound(cc.begin(), cc.end(), s[i] + M) - cc.begin();
            int y2 = upper_bound(cc.begin(), cc.end(), e[i] + M) - cc.begin();
            update(1, 0, n, x1, x2, x2);
            update(1, 0, n, y1, y2, y2);
        } else {
            int x1 = upper_bound(cc.begin(), cc.end(), s[i]) - cc.begin();
            int x2 = upper_bound(cc.begin(), cc.end(), e[i] + M) - cc.begin();
            update(1, 0, n, x1, x2, x2);
        }
    }

    for (int i = 1; i <= n; i++)
        up[0][i] = query(1, 0, n, i);
    for (int i = 1; i < LOGN; i++) {
        for (int j = 1; j <= n; j++)
            up[i][j] = up[i-1][up[i-1][j]];
    }

    for (int i = 1; i <= n; i++)
        try_i(i);

    if (mn == 1e7)
        mn = -1;
    cout << mn << "\n";
}

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