oj.uz

Submission #761951

# Submission time Handle Problem Language Result Execution time Memory
761951 2023-06-20T12:36:45 Z zsombor Event Hopping (BOI22_events) C++17
20 / 100
 276 ms 41960 KB 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct event {
    int s, e, ind;
    vector <pair <int, int>> Q;
};

int n, q;
vector <event> ev;
vector <int> new_ind(1e5 + 1);
//vector <node> sgt(3e5, node());
vector <int> Log(1e5, 0);
vector <vector <int>> st(2e5, vector<int>(17));
vector <vector <int>> lift(1e5, vector<int>(17));
vector <int> ans;

bool srt(event a, event b) {
    if (a.e < b.e) return true;
    if (a.e > b.e) return false;
    return (a.s < b.s ? true : false);
}

int bs(int val) {
    int a = -1, b = n - 1, c;
    while (b - a > 1) {
        c = (a + b) / 2;
        (ev[c].e < val ? a = c : b = c);
    }
    return b;
}

int mini(int a, int b) {
    return (ev[a].s < ev[b].s ? a : b);
}

int range_mini(int l, int r) {
    int j = Log[r - l + 1];
    return mini(st[l][j], st[r - (1 << j) + 1][j]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;
    ev.resize(n);
    ans.resize(q, 0);
    for (int i = 0; i < n; i++) {
        cin >> ev[i].s >> ev[i].e;
        ev[i].ind = i + 1;
    }
    sort(ev.begin(), ev.end(), srt);
    for (int i = 0; i < n; i++) new_ind[ev[i].ind] = i;

    int a, b;
    for (int i = 0; i < q; i++) {
        cin >> a >> b;
        a = new_ind[a];
        b = new_ind[b];
        ev[b].Q.push_back({ a,i });
    }

    for (int i = 2; i < 1e5; i++) Log[i] = Log[i / 2] + 1;
    for (int i = 0; i < n; i++) st[i][0] = i;
    for (int i = n; i < 2e5; i++) fill(st[i].begin(), st[i].end(), n - 1);
    for (int j = 1; j < 17; j++) {
        for (int i = 0; i < n; i++) {
            st[i][j] = mini(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }

    for (int i = 0; i < n; i++) {
        lift[i][0] = bs(ev[i].s);
        for (int j = 1; j < 17; j++) {
            a = range_mini(lift[i][j - 1], i);
            lift[i][j] = lift[a][j - 1];
        }
        for (auto& p : ev[i].Q) {
            a = p.first, b = i;
            if (ev[a].e == ev[b].e) continue;
            if (a > b) { ans[p.second] = (1 << 17); continue; }
            for (int j = 16; j >= 0; j--) {
                if (lift[b][j] <= a) continue;
                b = lift[b][j];
                ans[p.second] += (1 << j);
            }
            ans[p.second]++;
        }
    }

    for (int& i : ans) {
        if (i < (1 << 17)) cout << i << endl;
        else cout << "impossible\n";
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31656 KB Output is correct
2 Correct 232 ms 40540 KB Output is correct
3 Correct 250 ms 40660 KB Output is correct
4 Correct 259 ms 41164 KB Output is correct
5 Correct 233 ms 40808 KB Output is correct
6 Correct 251 ms 40784 KB Output is correct
7 Correct 276 ms 40748 KB Output is correct
8 Correct 152 ms 41164 KB Output is correct
9 Correct 125 ms 41156 KB Output is correct
10 Correct 196 ms 41932 KB Output is correct
11 Incorrect 174 ms 41940 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31652 KB Output is correct
2 Correct 21 ms 31644 KB Output is correct
3 Correct 29 ms 31700 KB Output is correct
4 Correct 22 ms 31672 KB Output is correct
5 Correct 23 ms 31676 KB Output is correct
6 Incorrect 23 ms 31720 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31652 KB Output is correct
2 Correct 21 ms 31644 KB Output is correct
3 Correct 29 ms 31700 KB Output is correct
4 Correct 22 ms 31672 KB Output is correct
5 Correct 23 ms 31676 KB Output is correct
6 Incorrect 23 ms 31720 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31652 KB Output is correct
2 Correct 21 ms 31644 KB Output is correct
3 Correct 29 ms 31700 KB Output is correct
4 Correct 22 ms 31672 KB Output is correct
5 Correct 23 ms 31676 KB Output is correct
6 Incorrect 23 ms 31720 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 237 ms 40556 KB Output is correct
2 Correct 248 ms 40728 KB Output is correct
3 Correct 266 ms 41184 KB Output is correct
4 Correct 138 ms 41168 KB Output is correct
5 Correct 224 ms 41960 KB Output is correct
6 Correct 264 ms 41764 KB Output is correct
7 Correct 260 ms 41664 KB Output is correct
8 Correct 214 ms 41772 KB Output is correct
9 Correct 105 ms 37488 KB Output is correct
10 Correct 251 ms 40512 KB Output is correct
11 Correct 218 ms 40324 KB Output is correct
12 Correct 252 ms 40496 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31656 KB Output is correct
2 Correct 232 ms 40540 KB Output is correct
3 Correct 250 ms 40660 KB Output is correct
4 Correct 259 ms 41164 KB Output is correct
5 Correct 233 ms 40808 KB Output is correct
6 Correct 251 ms 40784 KB Output is correct
7 Correct 276 ms 40748 KB Output is correct
8 Correct 152 ms 41164 KB Output is correct
9 Correct 125 ms 41156 KB Output is correct
10 Correct 196 ms 41932 KB Output is correct
11 Incorrect 174 ms 41940 KB Output isn't correct
12 Halted 0 ms 0 KB -