oj.uz

Submission #722373

# Submission time Handle Problem Language Result Execution time Memory
722373 2023-04-11T20:56:02 Z Itamar Event Hopping (BOI22_events) C++14
20 / 100
 394 ms 26088 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 (rii[bin[a][i]] < b) {
                    a = bin[a][i];
                    ans += 1 << i;
                }
            }

        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 Incorrect 0 ms 212 KB Output isn't correct
2 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 Incorrect 0 ms 212 KB Output isn't correct
3 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 Incorrect 0 ms 212 KB Output isn't correct
3 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 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 25652 KB Output is correct
2 Correct 342 ms 25660 KB Output is correct
3 Correct 318 ms 25596 KB Output is correct
4 Correct 331 ms 26088 KB Output is correct
5 Correct 394 ms 25972 KB Output is correct
6 Correct 384 ms 25832 KB Output is correct
7 Correct 375 ms 25748 KB Output is correct
8 Correct 366 ms 25888 KB Output is correct
9 Correct 139 ms 25028 KB Output is correct
10 Correct 382 ms 25388 KB Output is correct
11 Correct 342 ms 25252 KB Output is correct
12 Correct 355 ms 25424 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -