oj.uz

Submission #722371

# Submission time Handle Problem Language Result Execution time Memory
722371 2023-04-11T20:50:39 Z Itamar Event Hopping (BOI22_events) C++14
20 / 100
 351 ms 26228 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 Correct 0 ms 212 KB Output is correct
2 Correct 318 ms 25712 KB Output is correct
3 Correct 320 ms 25596 KB Output is correct
4 Correct 318 ms 25940 KB Output is correct
5 Correct 319 ms 25688 KB Output is correct
6 Correct 311 ms 25716 KB Output is correct
7 Correct 320 ms 25740 KB Output is correct
8 Correct 309 ms 26108 KB Output is correct
9 Correct 311 ms 26228 KB Output is correct
10 Correct 338 ms 26020 KB Output is correct
11 Incorrect 334 ms 26120 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 0 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 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 0 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 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 0 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 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 310 ms 25664 KB Output is correct
2 Correct 341 ms 25652 KB Output is correct
3 Correct 322 ms 25596 KB Output is correct
4 Correct 305 ms 26164 KB Output is correct
5 Correct 346 ms 26040 KB Output is correct
6 Correct 335 ms 25848 KB Output is correct
7 Correct 351 ms 25732 KB Output is correct
8 Correct 313 ms 25984 KB Output is correct
9 Correct 128 ms 25032 KB Output is correct
10 Correct 304 ms 25364 KB Output is correct
11 Correct 312 ms 25212 KB Output is correct
12 Correct 311 ms 25460 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 318 ms 25712 KB Output is correct
3 Correct 320 ms 25596 KB Output is correct
4 Correct 318 ms 25940 KB Output is correct
5 Correct 319 ms 25688 KB Output is correct
6 Correct 311 ms 25716 KB Output is correct
7 Correct 320 ms 25740 KB Output is correct
8 Correct 309 ms 26108 KB Output is correct
9 Correct 311 ms 26228 KB Output is correct
10 Correct 338 ms 26020 KB Output is correct
11 Incorrect 334 ms 26120 KB Output isn't correct
12 Halted 0 ms 0 KB -