oj.uz

Submission #762102

# Submission time Handle Problem Language Result Execution time Memory
762102 2023-06-20T20:08:34 Z zsombor Event Hopping (BOI22_events) C++17
20 / 100
 271 ms 42008 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 + 1, 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 23 ms 31572 KB Output is correct
2 Correct 238 ms 40560 KB Output is correct
3 Correct 245 ms 40696 KB Output is correct
4 Correct 253 ms 41120 KB Output is correct
5 Correct 238 ms 40768 KB Output is correct
6 Correct 240 ms 40740 KB Output is correct
7 Correct 234 ms 40796 KB Output is correct
8 Correct 139 ms 41168 KB Output is correct
9 Correct 131 ms 41184 KB Output is correct
10 Correct 189 ms 41964 KB Output is correct
11 Incorrect 181 ms 42008 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31572 KB Output is correct
2 Correct 23 ms 31652 KB Output is correct
3 Correct 24 ms 31652 KB Output is correct
4 Correct 25 ms 31648 KB Output is correct
5 Correct 25 ms 31572 KB Output is correct
6 Incorrect 25 ms 31620 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31572 KB Output is correct
2 Correct 23 ms 31652 KB Output is correct
3 Correct 24 ms 31652 KB Output is correct
4 Correct 25 ms 31648 KB Output is correct
5 Correct 25 ms 31572 KB Output is correct
6 Incorrect 25 ms 31620 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31572 KB Output is correct
2 Correct 23 ms 31652 KB Output is correct
3 Correct 24 ms 31652 KB Output is correct
4 Correct 25 ms 31648 KB Output is correct
5 Correct 25 ms 31572 KB Output is correct
6 Incorrect 25 ms 31620 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 238 ms 40512 KB Output is correct
2 Correct 247 ms 40728 KB Output is correct
3 Correct 253 ms 41204 KB Output is correct
4 Correct 128 ms 41196 KB Output is correct
5 Correct 198 ms 41936 KB Output is correct
6 Correct 271 ms 41676 KB Output is correct
7 Correct 259 ms 41784 KB Output is correct
8 Correct 215 ms 41812 KB Output is correct
9 Correct 105 ms 37460 KB Output is correct
10 Correct 256 ms 40444 KB Output is correct
11 Correct 222 ms 40332 KB Output is correct
12 Correct 250 ms 40528 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31572 KB Output is correct
2 Correct 238 ms 40560 KB Output is correct
3 Correct 245 ms 40696 KB Output is correct
4 Correct 253 ms 41120 KB Output is correct
5 Correct 238 ms 40768 KB Output is correct
6 Correct 240 ms 40740 KB Output is correct
7 Correct 234 ms 40796 KB Output is correct
8 Correct 139 ms 41168 KB Output is correct
9 Correct 131 ms 41184 KB Output is correct
10 Correct 189 ms 41964 KB Output is correct
11 Incorrect 181 ms 42008 KB Output isn't correct
12 Halted 0 ms 0 KB -