oj.uz

Submission #597342

# Submission time Handle Problem Language Result Execution time Memory
597342 2022-07-15T22:48:07 Z yanndev Event Hopping (BOI22_events) C++17
20 / 100
 430 ms 30348 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() {
    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 0 ms 468 KB Output is correct
2 Correct 322 ms 25088 KB Output is correct
3 Correct 347 ms 28204 KB Output is correct
4 Correct 430 ms 28116 KB Output is correct
5 Correct 363 ms 28464 KB Output is correct
6 Correct 360 ms 28680 KB Output is correct
7 Correct 368 ms 28724 KB Output is correct
8 Correct 363 ms 30348 KB Output is correct
9 Correct 370 ms 30164 KB Output is correct
10 Correct 353 ms 28544 KB Output is correct
11 Incorrect 373 ms 29232 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 1 ms 468 KB Output is correct
3 Correct 2 ms 744 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Incorrect 2 ms 736 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 1 ms 468 KB Output is correct
3 Correct 2 ms 744 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Incorrect 2 ms 736 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 1 ms 468 KB Output is correct
3 Correct 2 ms 744 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Incorrect 2 ms 736 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 326 ms 25164 KB Output is correct
2 Correct 355 ms 25188 KB Output is correct
3 Correct 410 ms 25188 KB Output is correct
4 Correct 390 ms 27220 KB Output is correct
5 Correct 346 ms 25556 KB Output is correct
6 Correct 379 ms 26812 KB Output is correct
7 Correct 411 ms 29840 KB Output is correct
8 Correct 372 ms 30072 KB Output is correct
9 Correct 185 ms 27964 KB Output is correct
10 Correct 351 ms 29528 KB Output is correct
11 Correct 369 ms 29320 KB Output is correct
12 Correct 427 ms 29536 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 322 ms 25088 KB Output is correct
3 Correct 347 ms 28204 KB Output is correct
4 Correct 430 ms 28116 KB Output is correct
5 Correct 363 ms 28464 KB Output is correct
6 Correct 360 ms 28680 KB Output is correct
7 Correct 368 ms 28724 KB Output is correct
8 Correct 363 ms 30348 KB Output is correct
9 Correct 370 ms 30164 KB Output is correct
10 Correct 353 ms 28544 KB Output is correct
11 Incorrect 373 ms 29232 KB Output isn't correct
12 Halted 0 ms 0 KB -