oj.uz

Submission #721894

# Submission time Handle Problem Language Result Execution time Memory
721894 2023-04-11T08:34:20 Z drdilyor Event Hopping (BOI22_events) C++17
20 / 100
 576 ms 27612 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
 
 
const int inf = 1e9 + 1e5;
struct event {
    int l, r, i;
};

struct segtree {
    int n;
    vector<pair<int,int>> t;
    segtree(int n) : n(n), t(n*4, {-1, -1}) {}
    void update(int i, const pair<int,int>& x) {
        t[i+=n] = x;
        for (i /= 2; i >= 1; i/= 2) {
            t[i] = max(t[i*2], t[i*2+1]);
        }
    }
    pair<int,int> query(int l, int r) {
        l += n;
        r += n;
        pair<int,int> res{-1,-1};
        while (l <= r) {
            if (l%2==1) res = max(res, t[l++]);
            if (r%2==0) res = max(res, t[r--]);
            l /= 2;
            r /= 2;
        }
        return res;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<event> ev(n), og;
    map<int,int> comp;
    int _i = 0;
    for (auto& [s, e, i] : ev) {
        cin >> s >> e;
        comp[s] = comp[e] = 0;
        i = _i++;
    }
    int k = 0;
    for (auto& mp : comp)
        mp.second = k++;
    for (auto& [s, e, i] : ev)
        s = comp[s], e = comp[e];
 
    og = ev;
    sort(ev.begin(), ev.end(), [&](auto& a, auto& b) {
        return a.r == b.r ? a.l < b.l : a.r < b.r ;
    });
    //for (auto[a,b,c] : ev) cout << a << ' ' << b << ' ' << c <<'\n';
 
    segtree mxr(k);

    for (int i = 0; i < n;i ++) {
        mxr.update(ev[i].l, {ev[i].r, i});
    }

    vector jmp(20, vector(n, -1));
    for (int i = 0; i < n; i++) {
        pair<int,int> mx = mxr.query(0, ev[i].r);
        if (mx.first != ev[i].r)
            jmp[0][i] = mx.second;
    }
    for (int j = 1; j < 20; j++)
        for (int i = 0; i < n;i++)
            if (jmp[j-1][i] != -1)
                jmp[j][i] = jmp[j-1][jmp[j-1][i]];

    vector<int> iof(n);
    for (int i = 0; i < n; i++)
        iof[ev[i].i] = i;


    while (m--) {
        int s, e;
        cin >> s >> e;
        s--;e--;
 
        if (s == e) {
            cout << "0\n";
            continue;
        }
        if (og[e].l <= og[s].r && og[s].r <= og[e].r) {
            cout << "1\n";
            continue;
        }
        if (og[e].r < og[s].r) {
            cout << "impossible\n";
            continue;
        }

        int si = iof[s], ei = iof[e];
 
        int res = 0;
        for (int j = 19; j >= 0; j--) {
            if (jmp[j][si] != -1 && ev[jmp[j][si]].r < ev[ei].l) {
                si = jmp[j][si];
                res += 1<<j;
            }
        }
        int j = jmp[0][si];
        if (j != -1 && jmp[0][j] != -1 && ev[ei].l <= ev[jmp[0][j]].r) {
            cout << res+2 << '\n';
        } else {
            cout << "impossible\n";
        }
    }
 
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 19256 KB Output is correct
2 Correct 451 ms 19312 KB Output is correct
3 Correct 448 ms 19264 KB Output is correct
4 Correct 438 ms 27612 KB Output is correct
5 Correct 475 ms 19596 KB Output is correct
6 Correct 576 ms 27284 KB Output is correct
7 Correct 568 ms 27292 KB Output is correct
8 Correct 550 ms 27464 KB Output is correct
9 Correct 282 ms 26464 KB Output is correct
10 Correct 469 ms 26956 KB Output is correct
11 Correct 467 ms 26916 KB Output is correct
12 Correct 443 ms 26984 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -