oj.uz

Submission #722368

# Submission time Handle Problem Language Result Execution time Memory
722368 2023-04-11T20:46:14 Z Itamar Event Hopping (BOI22_events) C++14
20 / 100
 387 ms 26108 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];
        int ans = 0;
        for (int i = 19; i >= 0; i--) {
            if (rii[bin[a][i]] < b) {
                a = bin[a][i];
                ans += 1 << i;
            }
        }
        if (a == b)cout << 0 << "\n";
        else if (a > b)cout << "impossible" << "\n";
        else if (rii[a] >= b) cout <<  1 << "\n";
        else if (rii[bin[a][0]] >= b)cout << ans + 2 << "\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 325 ms 25680 KB Output is correct
3 Correct 320 ms 25684 KB Output is correct
4 Correct 336 ms 25596 KB Output is correct
5 Correct 319 ms 25684 KB Output is correct
6 Correct 374 ms 25692 KB Output is correct
7 Correct 323 ms 25684 KB Output is correct
8 Correct 341 ms 26104 KB Output is correct
9 Correct 309 ms 26108 KB Output is correct
10 Correct 357 ms 25964 KB Output is correct
11 Incorrect 375 ms 26008 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 3 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Incorrect 2 ms 468 KB Output isn't correct
10 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 3 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Incorrect 2 ms 468 KB Output isn't correct
10 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 3 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Incorrect 2 ms 468 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 25652 KB Output is correct
2 Correct 332 ms 25576 KB Output is correct
3 Correct 321 ms 25576 KB Output is correct
4 Correct 331 ms 26100 KB Output is correct
5 Correct 332 ms 25984 KB Output is correct
6 Correct 387 ms 25720 KB Output is correct
7 Correct 372 ms 25724 KB Output is correct
8 Correct 349 ms 25888 KB Output is correct
9 Correct 138 ms 25028 KB Output is correct
10 Correct 331 ms 25460 KB Output is correct
11 Correct 331 ms 25452 KB Output is correct
12 Correct 322 ms 25440 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 325 ms 25680 KB Output is correct
3 Correct 320 ms 25684 KB Output is correct
4 Correct 336 ms 25596 KB Output is correct
5 Correct 319 ms 25684 KB Output is correct
6 Correct 374 ms 25692 KB Output is correct
7 Correct 323 ms 25684 KB Output is correct
8 Correct 341 ms 26104 KB Output is correct
9 Correct 309 ms 26108 KB Output is correct
10 Correct 357 ms 25964 KB Output is correct
11 Incorrect 375 ms 26008 KB Output isn't correct
12 Halted 0 ms 0 KB -