oj.uz

Submission #597348

# Submission time Handle Problem Language Result Execution time Memory
597348 2022-07-15T23:05:23 Z yanndev Event Hopping (BOI22_events) C++17
20 / 100
 202 ms 27232 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";
        }
    }
}

/*

7 1
1 2
3 4
1 5
6 7
5 10
10 20
15 20
1 6

*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 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 468 KB Output is correct
2 Incorrect 0 ms 468 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 468 KB Output is correct
2 Incorrect 0 ms 468 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 468 KB Output is correct
2 Incorrect 0 ms 468 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 109 ms 25332 KB Output is correct
2 Correct 177 ms 25116 KB Output is correct
3 Correct 202 ms 25080 KB Output is correct
4 Correct 166 ms 27232 KB Output is correct
5 Correct 177 ms 25528 KB Output is correct
6 Correct 174 ms 26948 KB Output is correct
7 Correct 193 ms 26812 KB Output is correct
8 Correct 147 ms 26952 KB Output is correct
9 Correct 109 ms 26156 KB Output is correct
10 Correct 146 ms 26540 KB Output is correct
11 Correct 150 ms 26364 KB Output is correct
12 Correct 147 ms 26584 KB Output is correct

Subtask #6
0 / 30.0

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