oj.uz

Submission #722378

# Submission time Handle Problem Language Result Execution time Memory
722378 2023-04-11T21:09:39 Z Itamar Event Hopping (BOI22_events) C++14
20 / 100
 403 ms 26200 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 (bin[a][0] >= b)cout << ans + 1 << "\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 384 ms 25576 KB Output is correct
3 Correct 334 ms 25600 KB Output is correct
4 Correct 343 ms 25568 KB Output is correct
5 Correct 351 ms 25868 KB Output is correct
6 Correct 325 ms 25664 KB Output is correct
7 Correct 321 ms 25920 KB Output is correct
8 Correct 352 ms 26140 KB Output is correct
9 Correct 310 ms 26200 KB Output is correct
10 Correct 403 ms 26028 KB Output is correct
11 Incorrect 354 ms 26052 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 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 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 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 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 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 338 ms 25656 KB Output is correct
2 Correct 319 ms 25584 KB Output is correct
3 Correct 378 ms 25596 KB Output is correct
4 Correct 313 ms 26100 KB Output is correct
5 Correct 389 ms 26048 KB Output is correct
6 Correct 347 ms 25876 KB Output is correct
7 Correct 371 ms 25824 KB Output is correct
8 Correct 357 ms 26092 KB Output is correct
9 Correct 139 ms 25012 KB Output is correct
10 Correct 334 ms 25404 KB Output is correct
11 Correct 316 ms 25372 KB Output is correct
12 Correct 355 ms 25388 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 384 ms 25576 KB Output is correct
3 Correct 334 ms 25600 KB Output is correct
4 Correct 343 ms 25568 KB Output is correct
5 Correct 351 ms 25868 KB Output is correct
6 Correct 325 ms 25664 KB Output is correct
7 Correct 321 ms 25920 KB Output is correct
8 Correct 352 ms 26140 KB Output is correct
9 Correct 310 ms 26200 KB Output is correct
10 Correct 403 ms 26028 KB Output is correct
11 Incorrect 354 ms 26052 KB Output isn't correct
12 Halted 0 ms 0 KB -