oj.uz

Submission #597343

# Submission time Handle Problem Language Result Execution time Memory
597343 2022-07-15T22:49:57 Z yanndev Event Hopping (BOI22_events) C++17
0 / 100
 232 ms 27240 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;
        }

     
        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 111 ms 25228 KB Output is correct
3 Correct 130 ms 25224 KB Output is correct
4 Correct 216 ms 25128 KB Output is correct
5 Correct 146 ms 25400 KB Output is correct
6 Correct 142 ms 25488 KB Output is correct
7 Correct 140 ms 25672 KB Output is correct
8 Correct 169 ms 27240 KB Output is correct
9 Correct 177 ms 27200 KB Output is correct
10 Incorrect 163 ms 25080 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 25116 KB Output is correct
2 Correct 136 ms 25188 KB Output is correct
3 Correct 232 ms 25144 KB Output is correct
4 Correct 156 ms 27180 KB Output is correct
5 Incorrect 179 ms 25096 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 111 ms 25228 KB Output is correct
3 Correct 130 ms 25224 KB Output is correct
4 Correct 216 ms 25128 KB Output is correct
5 Correct 146 ms 25400 KB Output is correct
6 Correct 142 ms 25488 KB Output is correct
7 Correct 140 ms 25672 KB Output is correct
8 Correct 169 ms 27240 KB Output is correct
9 Correct 177 ms 27200 KB Output is correct
10 Incorrect 163 ms 25080 KB Output isn't correct
11 Halted 0 ms 0 KB -