Submission #1002186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002186		LOLOLO	Fire (BOI24_fire)	C++17	100 / 100	405 ms	87128 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 4e5 + 10;
const int L = sqrt(N) + 10;
int nxt[N][20], is[N][20];

ll solve() {
    int n, m;
    cin >> n >> m;

    map <int, int> mp;

    vector <pair <int, int>> seg(n);
    for (auto &x : seg) {
        cin >> x.f >> x.s;
        mp[x.s], mp[x.f];
    }

    int timer = 0;
    for (auto &x : mp) {
        timer++;
        x.s = timer;
    }

    for (auto &x : seg) {
        x.f = mp[x.f];
        x.s = mp[x.s];
    }

    sort(all(seg));

    int j = 0, ov = 0, mx = 0;
    for (int i = 1; i <= timer; i++) {
        while (j < sz(seg) && seg[j].f <= i) {
            if (ov) {
                if (seg[j].f > seg[j].s) {
                    mx = max(mx, seg[j].s);
                }
            } else {
                if (seg[j].f > seg[j].s) {
                    ov = 1;
                    mx = seg[j].s;
                } else {
                    mx = max(mx, seg[j].s);
                }
            }
            j++;
        }

        if (mx) {
            nxt[i][0] = mx;
            is[i][0] = ov;
        } else {
            nxt[i][0] = i;
        }
    }

    if (ov) {
        for (int i = 1; i <= mx; i++) {
            if (is[i][0] == 0) {
                nxt[i][0] = max(nxt[i][0], mx);
            }
        }
    }

    for (int j = 1; j < 20; j++) {
        for (int i = 1; i <= timer; i++) {
            nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
            is[i][j] = is[i][j - 1] | is[nxt[i][j - 1]][j - 1];
        }
    }

    ll ans = 1e18;
    for (auto x : seg) {
        int l = 0, r = 0;
        ll cc = 1;
        if (x.f < x.s) {
            l = x.f, r = x.s;
            for (int j = 19; j >= 0; j--) {
                if (is[r][j] == 0) {
                    r = nxt[r][j];
                    cc = cc + ((ll)1 << j);
                }
            }

            if (is[r][0] == 0)
                continue;

            r = nxt[r][0];
            cc++;
        } else {
            r = x.s, l = x.f;
        }

        for (int j = 19; j >= 0; j--) {
            if (is[r][j] == 0 && nxt[r][j] < l) {
                r = nxt[r][j];
                cc = cc + ((ll)1 << j);
            }
        }

        if (is[r][0] || nxt[r][0] >= l) {
            ans = min(ans, cc + 1);
        }
    }

    if (ans > n)
        return -1;

    return ans;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
 
    int t = 1;
    //cin >> t;
 
    while (t--) {
        cout << solve() << '\n';
    }
 
    return 0;
} 

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