oj.uz

답안 #850076

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
850076 2023-09-15T17:29:17 Z MinaRagy06 Event Hopping (BOI22_events) C++17
30 / 100
 288 ms 73376 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])) {
                    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

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 51804 KB Output is correct
2 Correct 203 ms 64208 KB Output is correct
3 Correct 202 ms 64124 KB Output is correct
4 Correct 206 ms 64200 KB Output is correct
5 Correct 207 ms 64796 KB Output is correct
6 Correct 214 ms 65384 KB Output is correct
7 Correct 211 ms 65480 KB Output is correct
8 Correct 256 ms 69752 KB Output is correct
9 Correct 243 ms 69832 KB Output is correct
10 Correct 205 ms 64456 KB Output is correct
11 Correct 279 ms 66500 KB Output is correct
12 Correct 124 ms 61388 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 51800 KB Output is correct
2 Correct 8 ms 51892 KB Output is correct
3 Correct 10 ms 51800 KB Output is correct
4 Correct 9 ms 51804 KB Output is correct
5 Incorrect 9 ms 51804 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 51800 KB Output is correct
2 Correct 8 ms 51892 KB Output is correct
3 Correct 10 ms 51800 KB Output is correct
4 Correct 9 ms 51804 KB Output is correct
5 Incorrect 9 ms 51804 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 51800 KB Output is correct
2 Correct 8 ms 51892 KB Output is correct
3 Correct 10 ms 51800 KB Output is correct
4 Correct 9 ms 51804 KB Output is correct
5 Incorrect 9 ms 51804 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 64020 KB Output is correct
2 Correct 195 ms 64248 KB Output is correct
3 Correct 231 ms 64168 KB Output is correct
4 Correct 235 ms 69808 KB Output is correct
5 Correct 200 ms 64716 KB Output is correct
6 Correct 261 ms 69460 KB Output is correct
7 Correct 262 ms 69308 KB Output is correct
8 Correct 288 ms 69576 KB Output is correct
9 Correct 255 ms 73376 KB Output is correct
10 Correct 284 ms 69252 KB Output is correct
11 Correct 276 ms 69896 KB Output is correct
12 Correct 278 ms 68976 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 51804 KB Output is correct
2 Correct 203 ms 64208 KB Output is correct
3 Correct 202 ms 64124 KB Output is correct
4 Correct 206 ms 64200 KB Output is correct
5 Correct 207 ms 64796 KB Output is correct
6 Correct 214 ms 65384 KB Output is correct
7 Correct 211 ms 65480 KB Output is correct
8 Correct 256 ms 69752 KB Output is correct
9 Correct 243 ms 69832 KB Output is correct
10 Correct 205 ms 64456 KB Output is correct
11 Correct 279 ms 66500 KB Output is correct
12 Correct 124 ms 61388 KB Output is correct
13 Correct 8 ms 51800 KB Output is correct
14 Correct 8 ms 51892 KB Output is correct
15 Correct 10 ms 51800 KB Output is correct
16 Correct 9 ms 51804 KB Output is correct
17 Incorrect 9 ms 51804 KB Output isn't correct
18 Halted 0 ms 0 KB -