oj.uz

Submission #597344

# Submission time Handle Problem Language Result Execution time Memory
597344 2022-07-15T22:50:23 Z yanndev Event Hopping (BOI22_events) C++17
20 / 100
 194 ms 27284 KB 
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;

struct Inter {
    int rl;
    int rr;
    int id;
    bool operator<(const Inter& other) const {
        if (rr != other.rr)
            return rr < other.rr;
        if (rl != other.rl)
            return rl < other.rl;
        return id < other.id;
    }
};

const int MX_N = 1e5 + 42;
const int TREE_SIZE = (int)1 << 19;

int rl[MX_N];
int rr[MX_N];
int jump[20][MX_N];
int tree[2 * TREE_SIZE + 42];

void insert(int idx, int val, bool force = false) {
    idx += TREE_SIZE;
    if (force || rl[val] < rl[tree[idx]])
        tree[idx] = val;
    for (int i = idx / 2; i > 0; i /= 2) {
        if (rl[tree[2 * i]] < rl[tree[2 * i + 1]])
            tree[i] = tree[2 * i];
        else
            tree[i] = tree[2 * i + 1];
    }
}

int query(int left, int right) {
    left += TREE_SIZE;
    right += TREE_SIZE;

    int mnVal = 1e9;
    int id = -1;
    while (left <= right) {
        if (left % 2 == 1) {
            int newId = tree[left];
            if (rl[newId] < mnVal) {
                mnVal = rl[newId];
                id = newId;
            }
            left++;
        }

        if (right % 2 == 0) {
            int newId = tree[right];
            if (rl[newId] < mnVal) {
                mnVal = rl[newId];
                id = newId;
            }
            right--;
        }

        left /= 2;
        right /= 2;
    }

    return id;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;

    vector<Inter> ranges {};
    vector<int> vals {};

    for (int i = 0; i < n; i++) {
        cin >> rl[i] >> rr[i];
        vals.push_back(rl[i]);
        vals.push_back(rr[i]);
    }

    sort(vals.begin(), vals.end());
    vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
    
    for (int i = 0; i < n; i++) {
        rl[i] = lower_bound(vals.begin(), vals.end(), rl[i]) - vals.begin();
        rr[i] = lower_bound(vals.begin(), vals.end(), rr[i]) - vals.begin();
        ranges.push_back({rl[i], rr[i], i});
    }

    rl[n] = rr[n] = 1e9 + 42;
    for (int i = 0; i < (int)vals.size(); i++)
        insert(i, n, true);

    sort(ranges.begin(), ranges.end());
    for (int i = 0; i < n; i++) {
        //cout << "doing range " << ranges[i].id << ' ' << ranges[i].rl << ' ' << ranges[i].rr << '\n';
        jump[0][ranges[i].id] = query(ranges[i].rl, ranges[i].rr);
        //cout << "query is " << jump[0][ranges[i].id] << '\n';
        if (jump[0][ranges[i].id] == -1)
            jump[0][ranges[i].id] = ranges[i].id;

        //cout << "inserting at " << ranges[i].rr << '\n';
        insert(ranges[i].rr, ranges[i].id);
        //cout << "val at pos " << query(ranges[i].rr, ranges[i].rr) << '\n';
    }
    
    for (int i = 1; i <= 19; i++)
        for (int j = 0; j < n; j++)
            jump[i][j] = jump[i - 1][jump[i - 1][j]];

    for (int i = 0; i < q; i++) {
        int s, e;
        cin >> s >> e;
        s--, e--;

        if (s == e) {
            cout << "0\n";
            continue;
        }

        if (rl[e] <= rr[s] && rr[s] <= rr[e]) {
            cout << "1\n";
            continue;
        }

        if (rl[s] > rl[e]) {
            cout << "impossible\n";
            continue;
        }

        int ans = 0;

        //cout << "start has " << rl[s] << ' ' << rr[s] << '\n';
        //cout << "bef jump left is " << rl[e] << " right is " << rr[e] << '\n';

        for (int bit = 19; bit >= 0; bit--) {
            int nxt = jump[bit][e];
            if (rl[nxt] > rr[s]) {
                //cout << "nxt has " << rl[nxt] << ' ' << rr[nxt] << '\n';
                //cout << "jumping of " << (1 << bit) << '\n';
                ans += (1 << bit);
                e = nxt;
            }
        }

        //cout << "preans " << ans << '\n';
        //cout << "bef end left is " << rl[e] << " right is " << rr[e] << '\n';

        ans++;
        e = jump[0][e];
        //cout << "last jump left is " << rl[e] << " right is " << rr[e] << '\n';
        if (rl[e] <= rr[s]) {
            cout << ans + 1 << '\n';
        } else {
            cout << "impossible\n";
        }
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 122 ms 25168 KB Output is correct
3 Correct 131 ms 25220 KB Output is correct
4 Correct 189 ms 25128 KB Output is correct
5 Correct 158 ms 25360 KB Output is correct
6 Correct 140 ms 25572 KB Output is correct
7 Correct 142 ms 25648 KB Output is correct
8 Correct 154 ms 27276 KB Output is correct
9 Correct 156 ms 27284 KB Output is correct
10 Correct 143 ms 25532 KB Output is correct
11 Incorrect 167 ms 26164 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Incorrect 1 ms 724 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 115 ms 25288 KB Output is correct
2 Correct 172 ms 25132 KB Output is correct
3 Correct 194 ms 25200 KB Output is correct
4 Correct 155 ms 27260 KB Output is correct
5 Correct 142 ms 25592 KB Output is correct
6 Correct 184 ms 26904 KB Output is correct
7 Correct 161 ms 26824 KB Output is correct
8 Correct 143 ms 27128 KB Output is correct
9 Correct 107 ms 26152 KB Output is correct
10 Correct 147 ms 26452 KB Output is correct
11 Correct 137 ms 26316 KB Output is correct
12 Correct 143 ms 26580 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 122 ms 25168 KB Output is correct
3 Correct 131 ms 25220 KB Output is correct
4 Correct 189 ms 25128 KB Output is correct
5 Correct 158 ms 25360 KB Output is correct
6 Correct 140 ms 25572 KB Output is correct
7 Correct 142 ms 25648 KB Output is correct
8 Correct 154 ms 27276 KB Output is correct
9 Correct 156 ms 27284 KB Output is correct
10 Correct 143 ms 25532 KB Output is correct
11 Incorrect 167 ms 26164 KB Output isn't correct
12 Halted 0 ms 0 KB -