Submission #993203

#	Time	Username	Problem	Language	Result	Execution time	Memory
993203		vladilius	Fire (BOI24_fire)	C++17	0 / 100	2099 ms	348 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int inf = 2e9 + 5;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // freopen("ain1.txt", "r", stdin);

    int n, m; cin>>n>>m;

    vector<int> log(n + 1);
    for (int i = 2; i <= n; i++) log[i] = log[i / 2] + 1;

    vector<int> l(n + 1), r(n + 1);
    vector<pii> all = {{-1, -1}};
    bool ind = 1;
    for (int i = 1; i <= n; i++){
        cin>>l[i]>>r[i];
        if (!r[i]) r[i] = m;
        else r[i]--;
        if (l[i] > r[i]){
            r[i] += m;
            ind = 0;
        }
        all.pb({l[i], r[i]});
    }
    
    sort(all.begin() + 1, all.end());
    
    if (ind){
        int x = 0, i = 1, out = 0;
        while (i <= n && x <= m){
            int mx = -1;
            while (i <= n && all[i].ff <= x){
                mx = max(mx, all[i].ss);
            }
            if (mx == -1){
                cout<<-1<<"\n";
                return 0;
            }
            out++;
            x = mx + 1;
        }
        if (x > m) cout<<out<<"\n";
        else cout<<-1<<"\n";
        return 0;
    }

    vector<pii> nw = {{-1, -1}};
    int i = 1;
    while (i <= n){
        int j = i;
        while (j <= n && all[i].ff == all[j].ff) j++;
        nw.pb(all[j - 1]);
        i = j;
    }

    all = nw;
    n = all.size() - 1;

    auto cmp = [&](pii x, pii y){
        if (x.ss == y.ss) return x.ff < y.ff;
        return x.ss < y.ss;
    };

    sort(all.begin() + 1, all.end(), cmp);

    nw.clear();
    nw.pb({-1, -1});

    i = 1;
    while (i <= n){
        int j = i;
        while (j <= n && all[i].ss == all[j].ss) j++;
        nw.pb(all[i]);
        i = j;
    }

    all = nw;
    n = all.size() - 1;

    sort(all.begin() + 1, all.end());
    
    int lg = ceil(log2(n));

    vector<vector<pii>> sp(n + 1, vector<pii>(lg + 1));
    for (int i = 1; i <= n; i++){
        sp[i][0] = {all[i].ss, i};
    }
    for (int t = 1; t <= lg; t++){
        for (int i = 1; i + (1 << t) <= n + 1; i++){
            sp[i][t] = max(sp[i][t - 1], sp[i + (1 << (t - 1))][t - 1]);
        }
    }

    auto get_max = [&](int l, int r){
        int t = log[r - l + 1];
        return max(sp[l][t], sp[r - (1 << t) + 1][t]);
    };

    vector<int> ff;
    for (int i = 1; i <= n; i++) ff.pb(all[i].ff);
    vector<int> :: iterator it1, it2;

    vector<int> g(n + 1);
    for (int i = 1; i <= n; i++){
        int l = all[i].ff, r = all[i].ss + 1;

        it1 = lower_bound(ff.begin(), ff.end(), l);
        it2 = upper_bound(ff.begin(), ff.end(), r);
        int u = (it1 - ff.begin()) + 1, v = (it2 - ff.begin());
        pii b = get_max(u, v);
        if (b.ff >= r) g[i] = b.ss;
    }
    
    vector<int> x(n + 1);
    x[0] = inf;
    for (int i = 1; i <= n; i++){
        x[i] = all[i].ss + 1;
    }

    vector<vector<int>> pw(n + 1, vector<int>(lg + 1)), mx(n + 1, vector<int>(lg + 1));
    vector<bool> used(n + 1);
    used[0] = 1;
    function<void(int)> fill = [&](int v){
        if (used[v]) return;
        fill(g[v]);
        used[v] = 1;
        pw[v][0] = g[v];
        mx[v][0] = x[g[v]];
        for (int i = 1; i <= lg; i++){
            pw[v][i] = pw[pw[v][i - 1]][i - 1];
            mx[v][i] = max(mx[v][i - 1], mx[pw[v][i - 1]][i - 1]);
        }
    };
    
    for (int i = 1; i <= n; i++){
        fill(i);
    }

    auto get = [&](int v, int k){
        int ans = x[v];
        for (int i = lg; i >= 0; i--){
            if (k >= (1 << i)){
                k -= (1 << i);
                ans = max(ans, mx[v][i]);
                v = pw[v][i];
            }
        }
        return ans;
    };

    int out = n + 1;
    for (int i = 1; i <= n; i++){
        int lm = all[i].ff + m;
        int lb = 0, rb = n - 1;
        while (lb + 1 < rb){
            int m = (lb + rb) / 2;
            int v = get(i, m);
            if (v >= lm){
                rb = m;
            }
            else {
                lb = m + 1;
            }
        }
        if (get(i, rb) < lm) continue;
        if (get(i, lb) >= lm) rb = lb;
        if (get(i, rb) != inf) out = min(out, rb + 1);
    }

    if (out == n + 1) cout<<-1<<"\n";
    else cout<<out<<"\n";
}

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