oj.uz

Submission #1115109

# Submission time Handle Problem Language Result Execution time Memory
1115109 2024-11-20T04:18:58 Z _callmelucian Event Hopping (BOI22_events) C++14
20 / 100
 112 ms 16664 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e5 + 5;

struct item {
    int L, R;

    item() : L(INT_MAX), R(0) {}
    item (int L, int R) : L(L), R(R) {}

    bool operator < (const item &o) const {
        if (R == o.R) return L < o.L;
        return R < o.R;
    }
} event[mn];

struct IT {
    vector<int> tr;
    IT (int sz) : tr(4 * sz) {}

    int opr (int a, int b) {
        return (event[a].L < event[b].L ? a : b);
    }

    void update (int pos, int val, int k, int l, int r) {
        for (; l < r;) {
            int mid = (l + r) >> 1;
            if (pos <= mid) k <<= 1, r = mid;
            else k <<= 1, k |= 1, l = mid + 1;
        }

        tr[k] = opr(tr[k], val);
        for (k /= 2; k; k /= 2)
            tr[k] = opr(tr[k << 1], tr[k << 1 | 1]);
    }

    int query (int a, int b, int k, int l, int r) {
        if (b < l || r < a) return 0;
        if (a <= l && r <= b) return tr[k];
        int mid = (l + r) >> 1;
        return opr(query(a, b, 2 * k, l, mid), query(a, b, 2 * k + 1, mid + 1, r));
    }
};

vector<int> cmp;
int nxt[18][mn];

int getID (int targ) {
    return lower_bound(all(cmp), targ) - cmp.begin();
}

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

    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> event[i].L >> event[i].R;
        cmp.push_back(event[i].L), cmp.push_back(event[i].R);
    }
    sort(all(cmp)), filter(cmp);

    vector<int> ord(n);
    for (int i = 1; i <= n; i++) ord[i - 1] = i;
    sort(all(ord), [&] (int a, int b) { return event[a].R < event[b].R; });

    IT tree(cmp.size());
    for (int i : ord) {
        event[i].L = getID(event[i].L), event[i].R = getID(event[i].R);
        tree.update(event[i].R, i, 1, 0, cmp.size() - 1);
        nxt[0][i] = tree.query(event[i].L, event[i].R, 1, 0, cmp.size() - 1);

//        cout << "next " << i << " -> " << nxt[0][i] << "\n";
    }

    for (int s = 1; s < 18; s++)
        for (int i = 1; i <= n; i++)
            nxt[s][i] = nxt[s - 1][nxt[s - 1][i]];

    for (int i = 0; i < q; i++) {
        int s, e; cin >> s >> e;
        if (s == e) {
            cout << 0 << "\n";
            continue;
        }
        if (event[s].R > event[e].R) {
            cout << "impossible\n";
            continue;
        }
        if (event[e].L <= event[s].R) {
            cout << 1 << "\n";
            continue;
        }

        int ans = 0;
        for (int lift = 17; lift >= 0; lift--) {
            if (event[nxt[lift][e]].L > event[s].R) e = nxt[lift][e], ans |= (1 << lift);
        }
        e = nxt[0][e], ans++;

        if (event[e].L > event[s].R) cout << "impossible\n";
        else cout << ans + 1 << "\n";
    }


    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7248 KB Output is correct
2 Correct 87 ms 14512 KB Output is correct
3 Correct 98 ms 14532 KB Output is correct
4 Correct 111 ms 14560 KB Output is correct
5 Correct 108 ms 14792 KB Output is correct
6 Correct 102 ms 15044 KB Output is correct
7 Correct 97 ms 15044 KB Output is correct
8 Incorrect 96 ms 16664 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7248 KB Output is correct
2 Correct 2 ms 7248 KB Output is correct
3 Correct 3 ms 7436 KB Output is correct
4 Correct 3 ms 7500 KB Output is correct
5 Correct 3 ms 7248 KB Output is correct
6 Incorrect 3 ms 7248 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7248 KB Output is correct
2 Correct 2 ms 7248 KB Output is correct
3 Correct 3 ms 7436 KB Output is correct
4 Correct 3 ms 7500 KB Output is correct
5 Correct 3 ms 7248 KB Output is correct
6 Incorrect 3 ms 7248 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7248 KB Output is correct
2 Correct 2 ms 7248 KB Output is correct
3 Correct 3 ms 7436 KB Output is correct
4 Correct 3 ms 7500 KB Output is correct
5 Correct 3 ms 7248 KB Output is correct
6 Incorrect 3 ms 7248 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 14528 KB Output is correct
2 Correct 112 ms 14184 KB Output is correct
3 Correct 103 ms 14532 KB Output is correct
4 Correct 92 ms 16604 KB Output is correct
5 Correct 93 ms 15008 KB Output is correct
6 Correct 107 ms 16392 KB Output is correct
7 Correct 106 ms 16328 KB Output is correct
8 Correct 108 ms 14540 KB Output is correct
9 Correct 73 ms 14336 KB Output is correct
10 Correct 104 ms 16068 KB Output is correct
11 Correct 99 ms 15812 KB Output is correct
12 Correct 104 ms 16068 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7248 KB Output is correct
2 Correct 87 ms 14512 KB Output is correct
3 Correct 98 ms 14532 KB Output is correct
4 Correct 111 ms 14560 KB Output is correct
5 Correct 108 ms 14792 KB Output is correct
6 Correct 102 ms 15044 KB Output is correct
7 Correct 97 ms 15044 KB Output is correct
8 Incorrect 96 ms 16664 KB Output isn't correct
9 Halted 0 ms 0 KB -