oj.uz

Submission #850077

# Submission time Handle Problem Language Result Execution time Memory
850077 2023-09-15T17:30:42 Z MinaRagy06 Event Hopping (BOI22_events) C++17
100 / 100
 335 ms 75252 KB 
#include <bits/stdc++.h>
#define md ((l + r) >> 1)
using namespace std;
typedef int64_t ll;
 
const int N = 200'005;
array<int, 2> a[N];
int bl[18][N], bl2[18][N];
vector<array<int, 2>> st[2 * N], en[2 * N];
struct node {
    pair<int, int> mn;
    node() {mn = {1e9, -1};}
    node(pair<int, int> _mn) {mn = _mn;}
    friend node operator+(const node &l, const node &r) {
        return min(l.mn, r.mn);
    }
} seg[1 << 19];
void upd(int i, int l, int r, int x, pair<int, int> v) {
    if (x == l && r == x) {
        seg[i].mn = min(seg[i].mn, v);
        return;
    }
    if (r < x || x < l) {
        return;
    }
    upd(i << 1, l, md, x, v);
    upd(i << 1 | 1, md + 1, r, x, v);
    seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
node get(int i, int l, int r, int s, int e) {
    if (s <= l && r <= e) {
        return seg[i];
    }
    if (r < s || e < l) {
        return node();
    }
    return get(i << 1, l, md, s, e) + get(i << 1 | 1, md + 1, r, s, e);
}
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, q;
    cin >> n >> q;
    set<int> times;
    for (int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1];
        times.insert(a[i][0]), times.insert(a[i][1]);
    }
    vector<int> v;
    for (auto i : times) {
        v.push_back(i);
    }
    for (int i = 0; i < n; i++) {
        st[lower_bound(v.begin(), v.end(), a[i][0]) - v.begin()].push_back({i, a[i][1]});
        en[lower_bound(v.begin(), v.end(), a[i][1]) - v.begin()].push_back({i, a[i][1]});
    }
    multiset<array<int, 2>> s;
    for (int i = v.size() - 1; i >= 0; i--) {
        for (auto [idx, t] : en[i]) {
            s.insert({-t, idx});
        }
        for (auto [idx, t] : en[i]) {
            bl[0][idx] = (*s.begin())[1];
        }
        for (auto [idx, t] : st[i]) {
            s.erase(s.find({-t, idx}));
        }
    }
    for (int j = 1; j < 18; j++) {
        for (int i = 0; i < n; i++) {
            bl[j][i] = bl[j - 1][bl[j - 1][i]];
        }
    }
    s.clear();
    for (int i = 0; i < v.size(); i++) {
        st[i].clear();
        en[i].clear();
    }
    for (int i = 0; i < n; i++) {
        int pos = lower_bound(v.begin(), v.end(), a[i][1]) - v.begin();
        upd(1, 0, v.size() - 1, pos, {a[i][0], i});
    }
    for (int i = 0; i < n; i++) {
        int l = lower_bound(v.begin(), v.end(), a[i][0]) - v.begin();
        int r = lower_bound(v.begin(), v.end(), a[i][1]) - v.begin();
        bl2[0][i] = get(1, 0, v.size() - 1, l, r).mn.second;
    }
    for (int j = 1; j < 18; j++) {
        for (int i = 0; i < n; i++) {
            bl2[j][i] = bl2[j - 1][bl2[j - 1][i]];
        }
    }
    /*
    for (int i = 0; i < n; i++) {

        cout << bl2[0][i] << ' ';
    }
    cout << '\n';*/
    while (q--) {
        int s, e;
        cin >> s >> e;
        s--, e--;
        if (s == e) {
            cout << "0\n";
            continue;
        }
        if (a[e][0] <= a[s][1] && a[s][1] <= a[e][1]) {
            cout << "1\n";
            continue;
        }
        int ans = 0;
        for (int j = 17; j >= 0; j--) {
            int New = bl[j][s];
            if (!(a[e][0] <= a[New][1] && a[New][1] <= a[e][1]) && a[New][1] <= a[e][1]) {
                s = New;
                ans += (1 << j);
            }
        }
        if (a[bl[0][s]][1] > a[e][1]) {
            for (int j = 17; j >= 0; j--) {
                int New = bl2[j][e];
                if (!(a[New][0] <= a[s][1] && a[s][1] <= a[New][1]) && a[s][1] <= a[New][1]) {
                    e = New;
                    ans += 1 << j;
                }
            }
            ans++;
            e = bl2[0][e];
        } else {
            ans++;
            s = bl[0][s];
        }
        if (!(a[e][0] <= a[s][1] && a[s][1] <= a[e][1])) {
            cout << "impossible\n";
            continue;
        }
        cout << ans + 1 << '\n';
    }
    return 0;
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 51804 KB Output is correct
2 Correct 191 ms 64048 KB Output is correct
3 Correct 224 ms 64200 KB Output is correct
4 Correct 222 ms 64460 KB Output is correct
5 Correct 198 ms 64784 KB Output is correct
6 Correct 209 ms 65124 KB Output is correct
7 Correct 223 ms 65484 KB Output is correct
8 Correct 246 ms 69848 KB Output is correct
9 Correct 237 ms 69744 KB Output is correct
10 Correct 201 ms 64596 KB Output is correct
11 Correct 219 ms 66528 KB Output is correct
12 Correct 123 ms 61540 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 52052 KB Output is correct
2 Correct 8 ms 51804 KB Output is correct
3 Correct 9 ms 51804 KB Output is correct
4 Correct 9 ms 51804 KB Output is correct
5 Correct 9 ms 51892 KB Output is correct
6 Correct 9 ms 51844 KB Output is correct
7 Correct 12 ms 52060 KB Output is correct
8 Correct 10 ms 52056 KB Output is correct
9 Correct 8 ms 51804 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 52052 KB Output is correct
2 Correct 8 ms 51804 KB Output is correct
3 Correct 9 ms 51804 KB Output is correct
4 Correct 9 ms 51804 KB Output is correct
5 Correct 9 ms 51892 KB Output is correct
6 Correct 9 ms 51844 KB Output is correct
7 Correct 12 ms 52060 KB Output is correct
8 Correct 10 ms 52056 KB Output is correct
9 Correct 8 ms 51804 KB Output is correct
10 Correct 8 ms 51804 KB Output is correct
11 Correct 8 ms 51804 KB Output is correct
12 Correct 9 ms 51904 KB Output is correct
13 Correct 9 ms 51800 KB Output is correct
14 Correct 9 ms 51800 KB Output is correct
15 Correct 9 ms 51816 KB Output is correct
16 Correct 9 ms 52056 KB Output is correct
17 Correct 11 ms 52060 KB Output is correct
18 Correct 10 ms 51804 KB Output is correct
19 Correct 38 ms 53084 KB Output is correct
20 Correct 52 ms 52916 KB Output is correct
21 Correct 46 ms 53196 KB Output is correct
22 Correct 36 ms 54096 KB Output is correct
23 Correct 36 ms 54352 KB Output is correct
24 Correct 33 ms 54612 KB Output is correct
25 Correct 34 ms 53852 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 52052 KB Output is correct
2 Correct 8 ms 51804 KB Output is correct
3 Correct 9 ms 51804 KB Output is correct
4 Correct 9 ms 51804 KB Output is correct
5 Correct 9 ms 51892 KB Output is correct
6 Correct 9 ms 51844 KB Output is correct
7 Correct 12 ms 52060 KB Output is correct
8 Correct 10 ms 52056 KB Output is correct
9 Correct 8 ms 51804 KB Output is correct
10 Correct 8 ms 52056 KB Output is correct
11 Correct 8 ms 51804 KB Output is correct
12 Correct 9 ms 51804 KB Output is correct
13 Correct 9 ms 51804 KB Output is correct
14 Correct 9 ms 51804 KB Output is correct
15 Correct 10 ms 51804 KB Output is correct
16 Correct 11 ms 51924 KB Output is correct
17 Correct 10 ms 52060 KB Output is correct
18 Correct 10 ms 51904 KB Output is correct
19 Correct 183 ms 63468 KB Output is correct
20 Correct 183 ms 63640 KB Output is correct
21 Correct 220 ms 62044 KB Output is correct
22 Correct 207 ms 67460 KB Output is correct
23 Correct 258 ms 74796 KB Output is correct
24 Correct 267 ms 70484 KB Output is correct
25 Correct 67 ms 59672 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 64076 KB Output is correct
2 Correct 205 ms 64148 KB Output is correct
3 Correct 212 ms 64192 KB Output is correct
4 Correct 263 ms 69748 KB Output is correct
5 Correct 225 ms 64388 KB Output is correct
6 Correct 308 ms 69332 KB Output is correct
7 Correct 335 ms 69252 KB Output is correct
8 Correct 280 ms 69620 KB Output is correct
9 Correct 270 ms 73220 KB Output is correct
10 Correct 262 ms 68992 KB Output is correct
11 Correct 276 ms 69908 KB Output is correct
12 Correct 280 ms 68976 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 51804 KB Output is correct
2 Correct 191 ms 64048 KB Output is correct
3 Correct 224 ms 64200 KB Output is correct
4 Correct 222 ms 64460 KB Output is correct
5 Correct 198 ms 64784 KB Output is correct
6 Correct 209 ms 65124 KB Output is correct
7 Correct 223 ms 65484 KB Output is correct
8 Correct 246 ms 69848 KB Output is correct
9 Correct 237 ms 69744 KB Output is correct
10 Correct 201 ms 64596 KB Output is correct
11 Correct 219 ms 66528 KB Output is correct
12 Correct 123 ms 61540 KB Output is correct
13 Correct 8 ms 52052 KB Output is correct
14 Correct 8 ms 51804 KB Output is correct
15 Correct 9 ms 51804 KB Output is correct
16 Correct 9 ms 51804 KB Output is correct
17 Correct 9 ms 51892 KB Output is correct
18 Correct 9 ms 51844 KB Output is correct
19 Correct 12 ms 52060 KB Output is correct
20 Correct 10 ms 52056 KB Output is correct
21 Correct 8 ms 51804 KB Output is correct
22 Correct 8 ms 51804 KB Output is correct
23 Correct 8 ms 51804 KB Output is correct
24 Correct 9 ms 51904 KB Output is correct
25 Correct 9 ms 51800 KB Output is correct
26 Correct 9 ms 51800 KB Output is correct
27 Correct 9 ms 51816 KB Output is correct
28 Correct 9 ms 52056 KB Output is correct
29 Correct 11 ms 52060 KB Output is correct
30 Correct 10 ms 51804 KB Output is correct
31 Correct 38 ms 53084 KB Output is correct
32 Correct 52 ms 52916 KB Output is correct
33 Correct 46 ms 53196 KB Output is correct
34 Correct 36 ms 54096 KB Output is correct
35 Correct 36 ms 54352 KB Output is correct
36 Correct 33 ms 54612 KB Output is correct
37 Correct 34 ms 53852 KB Output is correct
38 Correct 8 ms 52056 KB Output is correct
39 Correct 8 ms 51804 KB Output is correct
40 Correct 9 ms 51804 KB Output is correct
41 Correct 9 ms 51804 KB Output is correct
42 Correct 9 ms 51804 KB Output is correct
43 Correct 10 ms 51804 KB Output is correct
44 Correct 11 ms 51924 KB Output is correct
45 Correct 10 ms 52060 KB Output is correct
46 Correct 10 ms 51904 KB Output is correct
47 Correct 183 ms 63468 KB Output is correct
48 Correct 183 ms 63640 KB Output is correct
49 Correct 220 ms 62044 KB Output is correct
50 Correct 207 ms 67460 KB Output is correct
51 Correct 258 ms 74796 KB Output is correct
52 Correct 267 ms 70484 KB Output is correct
53 Correct 67 ms 59672 KB Output is correct
54 Correct 198 ms 64076 KB Output is correct
55 Correct 205 ms 64148 KB Output is correct
56 Correct 212 ms 64192 KB Output is correct
57 Correct 263 ms 69748 KB Output is correct
58 Correct 225 ms 64388 KB Output is correct
59 Correct 308 ms 69332 KB Output is correct
60 Correct 335 ms 69252 KB Output is correct
61 Correct 280 ms 69620 KB Output is correct
62 Correct 270 ms 73220 KB Output is correct
63 Correct 262 ms 68992 KB Output is correct
64 Correct 276 ms 69908 KB Output is correct
65 Correct 280 ms 68976 KB Output is correct
66 Correct 9 ms 51800 KB Output is correct
67 Correct 206 ms 67328 KB Output is correct
68 Correct 199 ms 67272 KB Output is correct
69 Correct 229 ms 67272 KB Output is correct
70 Correct 218 ms 67792 KB Output is correct
71 Correct 205 ms 68264 KB Output is correct
72 Correct 212 ms 68556 KB Output is correct
73 Correct 239 ms 72828 KB Output is correct
74 Correct 235 ms 72944 KB Output is correct
75 Correct 216 ms 67828 KB Output is correct
76 Correct 216 ms 69724 KB Output is correct
77 Correct 122 ms 64196 KB Output is correct
78 Correct 9 ms 51800 KB Output is correct
79 Correct 9 ms 52060 KB Output is correct
80 Correct 9 ms 52052 KB Output is correct
81 Correct 9 ms 51804 KB Output is correct
82 Correct 9 ms 51960 KB Output is correct
83 Correct 10 ms 52208 KB Output is correct
84 Correct 10 ms 52160 KB Output is correct
85 Correct 8 ms 51804 KB Output is correct
86 Correct 38 ms 54044 KB Output is correct
87 Correct 34 ms 53852 KB Output is correct
88 Correct 40 ms 54120 KB Output is correct
89 Correct 36 ms 54180 KB Output is correct
90 Correct 35 ms 54352 KB Output is correct
91 Correct 32 ms 54612 KB Output is correct
92 Correct 34 ms 53840 KB Output is correct
93 Correct 177 ms 65476 KB Output is correct
94 Correct 165 ms 64716 KB Output is correct
95 Correct 193 ms 63692 KB Output is correct
96 Correct 182 ms 67472 KB Output is correct
97 Correct 249 ms 75252 KB Output is correct
98 Correct 234 ms 70660 KB Output is correct
99 Correct 49 ms 59836 KB Output is correct
100 Correct 297 ms 72384 KB Output is correct
101 Correct 283 ms 72540 KB Output is correct
102 Correct 256 ms 72700 KB Output is correct
103 Correct 281 ms 72152 KB Output is correct
104 Correct 303 ms 73064 KB Output is correct
105 Correct 260 ms 72096 KB Output is correct
106 Correct 207 ms 65476 KB Output is correct
107 Correct 240 ms 66572 KB Output is correct
108 Correct 252 ms 65740 KB Output is correct
109 Correct 247 ms 65676 KB Output is correct
110 Correct 327 ms 74788 KB Output is correct
111 Correct 307 ms 74720 KB Output is correct