oj.uz

Submission #1002155

# Submission time Handle Problem Language Result Execution time Memory
1002155 2024-06-19T10:33:33 Z LOLOLO Fire (BOI24_fire) C++17
0 / 100
 24 ms 2792 KB 
#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 == 1) {
        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) {
        if (x.f > x.s)
            continue;

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

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

        r = nxt[r][0];
        cc++;
        for (int j = 19; j >= 0; j--) {
            if (is[r][j] == 0 && nxt[r][j] < l) {
                r = nxt[r][j];
                cc += (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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 472 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 460 KB Output is correct
12 Correct 5 ms 2396 KB Output is correct
13 Correct 4 ms 1628 KB Output is correct
14 Correct 3 ms 1372 KB Output is correct
15 Incorrect 24 ms 2792 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -