oj.uz

Submission #722383

# Submission time Handle Problem Language Result Execution time Memory
722383 2023-04-11T21:23:32 Z Itamar Event Hopping (BOI22_events) C++14
20 / 100
 363 ms 26184 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 (rii[a] >= b)cout << ans + 1 << "\n";
        else cout << "impossible" << "\n";
        }
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 322 ms 25756 KB Output is correct
3 Correct 316 ms 25620 KB Output is correct
4 Correct 326 ms 25680 KB Output is correct
5 Correct 333 ms 25640 KB Output is correct
6 Correct 308 ms 25748 KB Output is correct
7 Correct 325 ms 25728 KB Output is correct
8 Correct 305 ms 26160 KB Output is correct
9 Correct 324 ms 26184 KB Output is correct
10 Correct 333 ms 26156 KB Output is correct
11 Incorrect 363 ms 26100 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 0 ms 212 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 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 0 ms 212 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 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 0 ms 212 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 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 325 ms 25640 KB Output is correct
2 Correct 326 ms 25624 KB Output is correct
3 Correct 315 ms 25716 KB Output is correct
4 Correct 324 ms 26100 KB Output is correct
5 Correct 333 ms 26012 KB Output is correct
6 Correct 357 ms 25904 KB Output is correct
7 Correct 352 ms 25728 KB Output is correct
8 Correct 329 ms 25928 KB Output is correct
9 Correct 125 ms 25072 KB Output is correct
10 Correct 318 ms 25416 KB Output is correct
11 Correct 325 ms 25252 KB Output is correct
12 Correct 324 ms 25444 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 322 ms 25756 KB Output is correct
3 Correct 316 ms 25620 KB Output is correct
4 Correct 326 ms 25680 KB Output is correct
5 Correct 333 ms 25640 KB Output is correct
6 Correct 308 ms 25748 KB Output is correct
7 Correct 325 ms 25728 KB Output is correct
8 Correct 305 ms 26160 KB Output is correct
9 Correct 324 ms 26184 KB Output is correct
10 Correct 333 ms 26156 KB Output is correct
11 Incorrect 363 ms 26100 KB Output isn't correct
12 Halted 0 ms 0 KB -