oj.uz

Submission #722357

# Submission time Handle Problem Language Result Execution time Memory
722357 2023-04-11T20:32:03 Z Itamar Event Hopping (BOI22_events) C++14
20 / 100
 372 ms 26456 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 << ans + 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 330 ms 25704 KB Output is correct
3 Correct 345 ms 25696 KB Output is correct
4 Correct 335 ms 25716 KB Output is correct
5 Correct 332 ms 25940 KB Output is correct
6 Correct 347 ms 25744 KB Output is correct
7 Correct 336 ms 25932 KB Output is correct
8 Correct 330 ms 26456 KB Output is correct
9 Correct 341 ms 26396 KB Output is correct
10 Correct 368 ms 26204 KB Output is correct
11 Incorrect 349 ms 26356 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 512 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 0 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 512 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 0 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 512 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 334 ms 25844 KB Output is correct
2 Correct 353 ms 25840 KB Output is correct
3 Correct 365 ms 25848 KB Output is correct
4 Correct 321 ms 26420 KB Output is correct
5 Correct 355 ms 26188 KB Output is correct
6 Correct 371 ms 26044 KB Output is correct
7 Correct 359 ms 25912 KB Output is correct
8 Correct 372 ms 26136 KB Output is correct
9 Correct 141 ms 25240 KB Output is correct
10 Correct 345 ms 25700 KB Output is correct
11 Correct 329 ms 25460 KB Output is correct
12 Correct 339 ms 25596 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 330 ms 25704 KB Output is correct
3 Correct 345 ms 25696 KB Output is correct
4 Correct 335 ms 25716 KB Output is correct
5 Correct 332 ms 25940 KB Output is correct
6 Correct 347 ms 25744 KB Output is correct
7 Correct 336 ms 25932 KB Output is correct
8 Correct 330 ms 26456 KB Output is correct
9 Correct 341 ms 26396 KB Output is correct
10 Correct 368 ms 26204 KB Output is correct
11 Incorrect 349 ms 26356 KB Output isn't correct
12 Halted 0 ms 0 KB -