oj.uz

Submission #722384

# Submission time Handle Problem Language Result Execution time Memory
722384 2023-04-11T21:24:14 Z Itamar Event Hopping (BOI22_events) C++14
20 / 100
 393 ms 26264 KB 
// rebel.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
using namespace std;
#include <vector>
#include <set>
#define pi pair<int,int>
#define vi vector<int>
#include <queue>
#include <algorithm>
#define ll long long

const int siz = 1e5;
int lii[siz];
int rii[siz];
int bin[siz][20];
int in[siz];
struct node {
    int l, r, mid;
    pi maxi;
    node* sl, * sr;
    node(int li, int ri) {
        l = li, r = ri, mid = (l + r) / 2;
        if (l < r) {
            sl = new node(l, mid);
            sr = new node(mid + 1, r);
            maxi = max(sl->maxi, sr->maxi);
        }
        else {
            maxi = { rii[l],l };
        }
    }
    pi query(int a, int b) {
        if (a > r || b < l)return { 0,0 };
        if (l >= a && r <= b)return maxi;
        return max(sl->query(a, b), sr->query(a, b));
    }
};
int main()
{
    int n, q;
    cin >> n >> q;
    vector<vi> vec;
    vi v1, v2;
    for (int i = 0; i < n; i++) {
        int s, e;
        cin >> s >> e;
        vec.push_back({ e,s,i });//

    }
    sort(vec.begin(), vec.end());
    for (vi p : vec) {
        v1.push_back(p[0]); v2.push_back(p[1]);
    }
    for (int i = 0; i < n; i++) {
        lii[i] = lower_bound(v1.begin(), v1.end(), v2[i]) - v1.begin();
        in[vec[i][2]] = i;
    }
    for (int i = 0; i < n; i++) {
        rii[n - 1 - i] = n - 1 - (lii[i]);
        in[i] = n - 1 - in[i];
    }
    node* seg = new node(0, n - 1);
    for (int i = 0; i < n; i++) {
        bin[i][0] = seg->query(i, rii[i]).second;
    }
    for (int i = 1; i < 20; i++) {
        for (int v = 0; v < n; v++) {
            bin[v][i] = bin[bin[v][i - 1]][i - 1];
        }
    }
    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        swap(a, b);
        a--, b--;
        a = in[a], b = in[b];
        if (a == b)cout << 0 << "\n";
        else if (a > b)cout << "impossible" << "\n";
        else if (rii[a] >= b) cout << 1 << "\n";
        else {
            int ans = 0;
            for (int i = 19; i >= 0; i--) {
                if (bin[a][i] < b) {
                    a = bin[a][i];
                    ans += 1 << i;
                }
            }

        if (bin[a][0] >= b)cout << ans + 1 << "\n";
        else cout << "impossible" << "\n";
        }
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 323 ms 25616 KB Output is correct
3 Correct 353 ms 25668 KB Output is correct
4 Correct 313 ms 25592 KB Output is correct
5 Correct 313 ms 25668 KB Output is correct
6 Correct 309 ms 25744 KB Output is correct
7 Correct 379 ms 25980 KB Output is correct
8 Correct 311 ms 26264 KB Output is correct
9 Correct 365 ms 26184 KB Output is correct
10 Correct 344 ms 26048 KB Output is correct
11 Incorrect 334 ms 26116 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Incorrect 2 ms 468 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Incorrect 2 ms 468 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Incorrect 2 ms 468 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 312 ms 25596 KB Output is correct
2 Correct 311 ms 25672 KB Output is correct
3 Correct 320 ms 25704 KB Output is correct
4 Correct 323 ms 26184 KB Output is correct
5 Correct 312 ms 25936 KB Output is correct
6 Correct 393 ms 25932 KB Output is correct
7 Correct 343 ms 25712 KB Output is correct
8 Correct 329 ms 25972 KB Output is correct
9 Correct 130 ms 25036 KB Output is correct
10 Correct 312 ms 25476 KB Output is correct
11 Correct 328 ms 25172 KB Output is correct
12 Correct 341 ms 25464 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 323 ms 25616 KB Output is correct
3 Correct 353 ms 25668 KB Output is correct
4 Correct 313 ms 25592 KB Output is correct
5 Correct 313 ms 25668 KB Output is correct
6 Correct 309 ms 25744 KB Output is correct
7 Correct 379 ms 25980 KB Output is correct
8 Correct 311 ms 26264 KB Output is correct
9 Correct 365 ms 26184 KB Output is correct
10 Correct 344 ms 26048 KB Output is correct
11 Incorrect 334 ms 26116 KB Output isn't correct
12 Halted 0 ms 0 KB -