oj.uz

Submission #698118

# Submission time Handle Problem Language Result Execution time Memory
698118 2023-02-12T12:14:04 Z Duy_e Event Hopping (BOI22_events) C++14
10 / 100
 219 ms 26812 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair <ll, ll>
#define nd second
#define st first
#define rep(i, n, m) for (ll i = (n); i <= (m); i ++)
#define rrep(i, n, m) for (ll i = (n); i >= (m); i --)
using namespace std;
const long long N = 2e5 + 5;
const long long INF = 2e9;
int f[N], n, q, pos[N], ans[N];
vector <int> st;
vector <int> in[N], queries[N];

struct events {
    int s, e, id;
    bool operator <(events other) {
        if (e == other.e) return s < other.s;
        return e < other.e;
    }
} a[N];

struct query {
    int u, v, id;
} qr[N];

namespace seg_assign {
    int n, st[4 * N];

    void init(int _n) {
        n = _n;
        memset(st, -1, sizeof st);
    }

    void push(int id) {
        if (st[id] == -1) return;
        st[id << 1] = st[id << 1 | 1] = st[id];
        st[id] = -1;
    }

    void upd(int id, int l, int r, int lef, int rig, int v) {
        if (l > rig || r < lef) return;
        if (lef <= l && r <= rig) {
            st[id] = v;
            return;
        }
        push(id);
        int mid = (l + r) >> 1;
        upd(id << 1, l, mid, lef, rig, v);
        upd(id << 1 | 1, mid + 1, r, lef, rig, v);
    }

    void upd(int l, int r, int v) {
        upd(1, 1, n, l, r, v);
    }

    int get(int id, int l, int r, int i) {
        if (l == r) return st[id];
        push(id);
        int mid = (l + r) >> 1;
        if (mid >= i) return get(id << 1, l, mid, i);
        return get(id << 1 | 1, mid + 1, r, i);
    }

    int get(int i) {
        return get(1, 1, n, i);
    }
}

namespace seg_min {
    int n, st[4 * N];

    void init(int _n) {
        n = _n;
        rep(i, 0, 4 * N - 1) st[i] = INF;
    }

    void upd(int id, int l, int r, int i, int v) {
        if (l > i || r < i) return;
        if (l == r) {
            st[id] = min(st[id], v);
            return;
        }

        int mid = (l + r) >> 1;
        upd(id << 1, l, mid, i, v); upd(id << 1 | 1, mid + 1, r, i, v);
        st[id] = min(st[id << 1], st[id << 1 | 1]);
    }

    void upd(int i, int v) {
        upd(1, 1, n, i, v);
    }

    int get(int id, int l, int r, int lef, int rig) {
        if (l > rig || r < lef) return INF;
        if (lef <= l && r <= rig) return st[id];
        int mid = (l + r) >> 1;
        return min(
            get(id << 1, l, mid, lef, rig),
            get(id << 1 | 1, mid + 1, r, lef, rig)
        );
    }

    int get(int l, int r) {
        return get(1, 1, n, l, r);
    }
}

vector <int> cmp;

void read() {
    cin >> n >> q;
    rep(i, 1, n) {
        cin >> a[i].s >> a[i].e;
        a[i].id = i;
        cmp.push_back(a[i].s);
        cmp.push_back(a[i].e);
    }

    sort(cmp.begin(), cmp.end());
    cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());

    auto find = [&](int x) {
        return lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin() + 1;
    };

    rep(i, 1, n) {
        a[i].s = find(a[i].s);
        a[i].e = find(a[i].e);
    }
}

void solve() {
    rep(i, 1, n) {
        in[a[i].e].push_back(i);

    }
    rep(i, 1, q) {
        ans[i] = INF;
        cin >> qr[i].u >> qr[i].v;
        if (a[qr[i].u].e > a[qr[i].v].e) continue;
        if (qr[i].u == qr[i].v)
            ans[i] = 0;
        else
            queries[qr[i].v].push_back(i);
    }

    auto cmp = [&](int i, int j) {
        return a[i].s > a[j].s;
    };

    seg_min :: init(2 * n);
    seg_assign :: init(2 * n);

    //rep(i, 1, n) seg_min :: upd(a[i].e, a[i].s);
    rep(i, 1, 2 * n) {
        sort(in[i].begin(), in[i].end(), cmp);

//in[i] luu chi so nhung con ket thuc tai i
        for (int id: in[i]) {
            while ((st.size() && a[st.back()].s >= a[id].s) ||
                   (st.size() > 1 && a[st[st.size() - 2]].e >= a[id].s)) {
                int j = st.back();
                st.pop_back();
                seg_assign :: upd(a[j].s, a[j].e, (int)st.size());
            }

            st.push_back(id);
            seg_min :: upd(a[id].e, a[id].s);
            f[i] = seg_min :: get(a[id].s, a[id].e);
            seg_min :: upd(i, f[i]);
            seg_assign :: upd(a[id].s, a[id].e, (int)st.size());

            int v = id;
            for (int j: queries[v]) {
                int u = qr[j].u;
                if (f[i] > a[u].e) continue;
                int tmp = seg_assign :: get(a[u].e);
                ans[j] = min(ans[j], (int)st.size() - tmp + 1);
            }
        }

        for (int id: in[i]) for (int j: queries[id]) {
            int u = qr[j].u;
            if (f[i] > a[u].e) continue;
            int tmp = seg_assign :: get(a[u].e);
            ans[j] = min(ans[j], (int)st.size() - tmp + 2);
        }
    }

    rep(i, 1, q) {
        if (ans[i] >= INF)
            cout << "impossible\n";
        else
            cout << ans[i] << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

//    freopen("events.inp", "r", stdin);
//    freopen("events.out", "w", stdout);

    read();
    solve();
    return 0;
}


/*

sort(events)
f[u] = min range current activating
query index of range -> [f[i], i]

query get ans
delete range -> set <pii> ? stack ? vector ? deque -> stack

f[u] ? min f[i], i belong to [su, eu]

everytime pop one element from stack -> upd index? ->
-> assign with stack size -> get = stack size - ans = index
get ans = fens

45m
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 169 ms 25464 KB Output is correct
3 Correct 175 ms 25648 KB Output is correct
4 Correct 190 ms 26784 KB Output is correct
5 Correct 176 ms 25800 KB Output is correct
6 Correct 181 ms 25820 KB Output is correct
7 Correct 174 ms 25828 KB Output is correct
8 Correct 193 ms 26676 KB Output is correct
9 Correct 168 ms 26548 KB Output is correct
10 Correct 203 ms 26620 KB Output is correct
11 Correct 185 ms 26388 KB Output is correct
12 Correct 116 ms 24032 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16004 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 8 ms 16012 KB Output is correct
4 Correct 8 ms 16084 KB Output is correct
5 Correct 10 ms 16004 KB Output is correct
6 Correct 9 ms 16048 KB Output is correct
7 Incorrect 9 ms 16008 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16004 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 8 ms 16012 KB Output is correct
4 Correct 8 ms 16084 KB Output is correct
5 Correct 10 ms 16004 KB Output is correct
6 Correct 9 ms 16048 KB Output is correct
7 Incorrect 9 ms 16008 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16004 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 8 ms 16012 KB Output is correct
4 Correct 8 ms 16084 KB Output is correct
5 Correct 10 ms 16004 KB Output is correct
6 Correct 9 ms 16048 KB Output is correct
7 Incorrect 9 ms 16008 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 25500 KB Output is correct
2 Correct 171 ms 25724 KB Output is correct
3 Correct 189 ms 26812 KB Output is correct
4 Correct 164 ms 26568 KB Output is correct
5 Correct 178 ms 26604 KB Output is correct
6 Incorrect 219 ms 25900 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 169 ms 25464 KB Output is correct
3 Correct 175 ms 25648 KB Output is correct
4 Correct 190 ms 26784 KB Output is correct
5 Correct 176 ms 25800 KB Output is correct
6 Correct 181 ms 25820 KB Output is correct
7 Correct 174 ms 25828 KB Output is correct
8 Correct 193 ms 26676 KB Output is correct
9 Correct 168 ms 26548 KB Output is correct
10 Correct 203 ms 26620 KB Output is correct
11 Correct 185 ms 26388 KB Output is correct
12 Correct 116 ms 24032 KB Output is correct
13 Correct 8 ms 16004 KB Output is correct
14 Correct 8 ms 15956 KB Output is correct
15 Correct 8 ms 16012 KB Output is correct
16 Correct 8 ms 16084 KB Output is correct
17 Correct 10 ms 16004 KB Output is correct
18 Correct 9 ms 16048 KB Output is correct
19 Incorrect 9 ms 16008 KB Output isn't correct
20 Halted 0 ms 0 KB -