oj.uz

Submission #949775

# Submission time Handle Problem Language Result Execution time Memory
949775 2024-03-19T16:54:00 Z Dec0Dedd Event Hopping (BOI22_events) C++14
100 / 100
 487 ms 53904 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N  = 2e5+100;
const int INF = 1e9+10;
const int K = 20;

struct segtree {
    vector<pii> t;

    void init(int sz) {
        t.resize(4*sz+10);
        for (auto &u : t) u={INF, -INF};
    }

    void upd(int v, int l, int r, int p, pii x) {
        if (l == r) {
            t[v]=min(t[v], x);
            return;
        } int m=(l+r)/2;
        if (p <= m) upd(2*v, l, m, p, x);
        else upd(2*v+1, m+1, r, p, x);
        t[v]=min(t[2*v], t[2*v+1]);
    }

    pii que(int v, int l, int r, int ql, int qr) {
        if (l > qr || r < ql) return {INF, -INF};
        if (l >= ql && r <= qr) return t[v];
        int m=(l+r)/2;
        return min(que(2*v, l, m, ql, qr), que(2*v+1, m+1, r, ql, qr));
    }
};

int s[N], e[N], p[N], n, q, up[K][N];

vector<int> G[N];

void pre(int v, int pr) {
    up[0][v]=pr;
    for (int i=1; i<K; ++i) up[i][v]=up[i-1][up[i-1][v]];
    for (auto u : G[v]) pre(u, v);
}

void solve() {
    cin>>n>>q;

    set<int> st;
    for (int i=1; i<=n; ++i) {
        cin>>s[i]>>e[i];
        st.insert(s[i]), st.insert(e[i]);
    }

    map<int, int> sc; int i=1;
    for (auto u : st) sc[u]=i++;
    for (int i=1; i<=n; ++i) s[i]=sc[s[i]], e[i]=sc[e[i]];

    segtree tr; tr.init(N);
    for (int i=1; i<=n; ++i) tr.upd(1, 1, N, e[i], {s[i], i});

    for (int i=1; i<=n; ++i) {
        pii x=tr.que(1, 1, N, s[i], e[i]);
        if (x.first >= s[i]) p[i]=i;
        else p[i]=x.second;
        if (p[i] != i) G[p[i]].push_back(i);
    }

    for (int i=1; i<=n; ++i) {
        if (p[i] == i) {
            pre(i, i);
        }
    }

    while (q--) {
        int l, r; cin>>l>>r;

        if (l == r) {
            cout<<0<<"\n";
            continue;
        }

        int ans=0;
        for (int i=K-1; i>=0; --i) {
            if (i > 0 && up[i][r] == up[i-1][r]) continue;
            if (s[up[i][r]] > s[l]) ans+=(1<<i), r=up[i][r];
        }

        //cout<<"HERE "<<r<<"\n";
        if (s[r] <= e[l] && e[l] <= e[r]) cout<<ans+1<<"\n";
        else {
            r=up[0][r], ++ans;
            if (s[r] <= e[l] && e[l] <= e[r]) cout<<ans+1<<"\n";
            else cout<<"impossible\n";
        }
    }
}

int main() {
    int t=1; //cin>>t;
    while (t--) solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 27228 KB Output is correct
2 Correct 364 ms 47328 KB Output is correct
3 Correct 367 ms 47188 KB Output is correct
4 Correct 375 ms 47316 KB Output is correct
5 Correct 375 ms 47600 KB Output is correct
6 Correct 371 ms 48208 KB Output is correct
7 Correct 367 ms 48284 KB Output is correct
8 Correct 371 ms 51228 KB Output is correct
9 Correct 362 ms 51024 KB Output is correct
10 Correct 377 ms 46264 KB Output is correct
11 Correct 378 ms 48328 KB Output is correct
12 Correct 276 ms 40872 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27228 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 7 ms 27484 KB Output is correct
4 Correct 8 ms 27480 KB Output is correct
5 Correct 7 ms 27484 KB Output is correct
6 Correct 7 ms 27512 KB Output is correct
7 Correct 7 ms 27480 KB Output is correct
8 Correct 9 ms 27740 KB Output is correct
9 Correct 6 ms 27228 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27228 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 7 ms 27484 KB Output is correct
4 Correct 8 ms 27480 KB Output is correct
5 Correct 7 ms 27484 KB Output is correct
6 Correct 7 ms 27512 KB Output is correct
7 Correct 7 ms 27480 KB Output is correct
8 Correct 9 ms 27740 KB Output is correct
9 Correct 6 ms 27228 KB Output is correct
10 Correct 6 ms 27228 KB Output is correct
11 Correct 6 ms 27228 KB Output is correct
12 Correct 7 ms 27516 KB Output is correct
13 Correct 7 ms 27484 KB Output is correct
14 Correct 7 ms 27484 KB Output is correct
15 Correct 7 ms 27484 KB Output is correct
16 Correct 8 ms 27484 KB Output is correct
17 Correct 8 ms 27484 KB Output is correct
18 Correct 7 ms 27224 KB Output is correct
19 Correct 179 ms 29780 KB Output is correct
20 Correct 169 ms 29640 KB Output is correct
21 Correct 174 ms 29948 KB Output is correct
22 Correct 170 ms 29892 KB Output is correct
23 Correct 174 ms 29856 KB Output is correct
24 Correct 169 ms 30036 KB Output is correct
25 Correct 175 ms 29952 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27228 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 7 ms 27484 KB Output is correct
4 Correct 8 ms 27480 KB Output is correct
5 Correct 7 ms 27484 KB Output is correct
6 Correct 7 ms 27512 KB Output is correct
7 Correct 7 ms 27480 KB Output is correct
8 Correct 9 ms 27740 KB Output is correct
9 Correct 6 ms 27228 KB Output is correct
10 Correct 6 ms 27228 KB Output is correct
11 Correct 6 ms 27228 KB Output is correct
12 Correct 7 ms 27484 KB Output is correct
13 Correct 7 ms 27484 KB Output is correct
14 Correct 8 ms 27540 KB Output is correct
15 Correct 7 ms 27484 KB Output is correct
16 Correct 7 ms 27484 KB Output is correct
17 Correct 7 ms 27484 KB Output is correct
18 Correct 6 ms 27228 KB Output is correct
19 Correct 208 ms 45696 KB Output is correct
20 Correct 179 ms 44880 KB Output is correct
21 Correct 190 ms 40016 KB Output is correct
22 Correct 211 ms 46180 KB Output is correct
23 Correct 262 ms 49356 KB Output is correct
24 Correct 271 ms 52048 KB Output is correct
25 Correct 63 ms 29416 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 47184 KB Output is correct
2 Correct 362 ms 47332 KB Output is correct
3 Correct 368 ms 47188 KB Output is correct
4 Correct 369 ms 50900 KB Output is correct
5 Correct 367 ms 46008 KB Output is correct
6 Correct 444 ms 53748 KB Output is correct
7 Correct 423 ms 53584 KB Output is correct
8 Correct 407 ms 52308 KB Output is correct
9 Correct 241 ms 49288 KB Output is correct
10 Correct 420 ms 53328 KB Output is correct
11 Correct 423 ms 52820 KB Output is correct
12 Correct 421 ms 53328 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 27228 KB Output is correct
2 Correct 364 ms 47328 KB Output is correct
3 Correct 367 ms 47188 KB Output is correct
4 Correct 375 ms 47316 KB Output is correct
5 Correct 375 ms 47600 KB Output is correct
6 Correct 371 ms 48208 KB Output is correct
7 Correct 367 ms 48284 KB Output is correct
8 Correct 371 ms 51228 KB Output is correct
9 Correct 362 ms 51024 KB Output is correct
10 Correct 377 ms 46264 KB Output is correct
11 Correct 378 ms 48328 KB Output is correct
12 Correct 276 ms 40872 KB Output is correct
13 Correct 6 ms 27228 KB Output is correct
14 Correct 5 ms 27228 KB Output is correct
15 Correct 7 ms 27484 KB Output is correct
16 Correct 8 ms 27480 KB Output is correct
17 Correct 7 ms 27484 KB Output is correct
18 Correct 7 ms 27512 KB Output is correct
19 Correct 7 ms 27480 KB Output is correct
20 Correct 9 ms 27740 KB Output is correct
21 Correct 6 ms 27228 KB Output is correct
22 Correct 6 ms 27228 KB Output is correct
23 Correct 6 ms 27228 KB Output is correct
24 Correct 7 ms 27516 KB Output is correct
25 Correct 7 ms 27484 KB Output is correct
26 Correct 7 ms 27484 KB Output is correct
27 Correct 7 ms 27484 KB Output is correct
28 Correct 8 ms 27484 KB Output is correct
29 Correct 8 ms 27484 KB Output is correct
30 Correct 7 ms 27224 KB Output is correct
31 Correct 179 ms 29780 KB Output is correct
32 Correct 169 ms 29640 KB Output is correct
33 Correct 174 ms 29948 KB Output is correct
34 Correct 170 ms 29892 KB Output is correct
35 Correct 174 ms 29856 KB Output is correct
36 Correct 169 ms 30036 KB Output is correct
37 Correct 175 ms 29952 KB Output is correct
38 Correct 6 ms 27228 KB Output is correct
39 Correct 6 ms 27228 KB Output is correct
40 Correct 7 ms 27484 KB Output is correct
41 Correct 7 ms 27484 KB Output is correct
42 Correct 8 ms 27540 KB Output is correct
43 Correct 7 ms 27484 KB Output is correct
44 Correct 7 ms 27484 KB Output is correct
45 Correct 7 ms 27484 KB Output is correct
46 Correct 6 ms 27228 KB Output is correct
47 Correct 208 ms 45696 KB Output is correct
48 Correct 179 ms 44880 KB Output is correct
49 Correct 190 ms 40016 KB Output is correct
50 Correct 211 ms 46180 KB Output is correct
51 Correct 262 ms 49356 KB Output is correct
52 Correct 271 ms 52048 KB Output is correct
53 Correct 63 ms 29416 KB Output is correct
54 Correct 355 ms 47184 KB Output is correct
55 Correct 362 ms 47332 KB Output is correct
56 Correct 368 ms 47188 KB Output is correct
57 Correct 369 ms 50900 KB Output is correct
58 Correct 367 ms 46008 KB Output is correct
59 Correct 444 ms 53748 KB Output is correct
60 Correct 423 ms 53584 KB Output is correct
61 Correct 407 ms 52308 KB Output is correct
62 Correct 241 ms 49288 KB Output is correct
63 Correct 420 ms 53328 KB Output is correct
64 Correct 423 ms 52820 KB Output is correct
65 Correct 421 ms 53328 KB Output is correct
66 Correct 5 ms 27228 KB Output is correct
67 Correct 361 ms 47952 KB Output is correct
68 Correct 362 ms 47444 KB Output is correct
69 Correct 371 ms 47444 KB Output is correct
70 Correct 394 ms 47892 KB Output is correct
71 Correct 387 ms 48208 KB Output is correct
72 Correct 371 ms 48212 KB Output is correct
73 Correct 375 ms 51120 KB Output is correct
74 Correct 381 ms 51332 KB Output is correct
75 Correct 399 ms 46400 KB Output is correct
76 Correct 401 ms 48464 KB Output is correct
77 Correct 284 ms 41048 KB Output is correct
78 Correct 6 ms 27228 KB Output is correct
79 Correct 8 ms 27484 KB Output is correct
80 Correct 9 ms 27512 KB Output is correct
81 Correct 7 ms 27484 KB Output is correct
82 Correct 8 ms 27520 KB Output is correct
83 Correct 8 ms 27536 KB Output is correct
84 Correct 8 ms 27644 KB Output is correct
85 Correct 7 ms 27228 KB Output is correct
86 Correct 185 ms 29472 KB Output is correct
87 Correct 186 ms 29644 KB Output is correct
88 Correct 191 ms 29872 KB Output is correct
89 Correct 176 ms 29780 KB Output is correct
90 Correct 179 ms 30036 KB Output is correct
91 Correct 180 ms 29952 KB Output is correct
92 Correct 172 ms 29832 KB Output is correct
93 Correct 222 ms 45768 KB Output is correct
94 Correct 213 ms 44832 KB Output is correct
95 Correct 205 ms 40144 KB Output is correct
96 Correct 231 ms 46136 KB Output is correct
97 Correct 268 ms 49364 KB Output is correct
98 Correct 282 ms 52028 KB Output is correct
99 Correct 67 ms 29308 KB Output is correct
100 Correct 487 ms 53808 KB Output is correct
101 Correct 432 ms 53904 KB Output is correct
102 Correct 447 ms 52484 KB Output is correct
103 Correct 466 ms 53548 KB Output is correct
104 Correct 469 ms 52564 KB Output is correct
105 Correct 449 ms 53472 KB Output is correct
106 Correct 351 ms 43260 KB Output is correct
107 Correct 388 ms 46964 KB Output is correct
108 Correct 382 ms 42016 KB Output is correct
109 Correct 362 ms 41932 KB Output is correct
110 Correct 455 ms 51240 KB Output is correct
111 Correct 458 ms 51168 KB Output is correct