oj.uz

Submission #722350

# Submission time Handle Problem Language Result Execution time Memory
722350 2023-04-11T20:21:05 Z Itamar Event Hopping (BOI22_events) C++14
20 / 100
 396 ms 29388 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, 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];
        }
    }
    int query(int a, int b) {
        if (a > r || b < l)return 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]);
    }
    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 (bin[a][i] < b) {
                a = bin[a][i];
                ans += 2 << 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 (bin[a][0] >= b)cout << ans + 2 << "\n";
        else cout << "impossible" << "\n";
    }
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 326 ms 25824 KB Output is correct
3 Correct 305 ms 25920 KB Output is correct
4 Correct 317 ms 25836 KB Output is correct
5 Correct 331 ms 26220 KB Output is correct
6 Correct 316 ms 25640 KB Output is correct
7 Correct 358 ms 26228 KB Output is correct
8 Correct 310 ms 29388 KB Output is correct
9 Correct 332 ms 29188 KB Output is correct
10 Correct 369 ms 29044 KB Output is correct
11 Incorrect 343 ms 29176 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 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 1 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 1 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 331 ms 26956 KB Output is correct
2 Correct 334 ms 26392 KB Output is correct
3 Correct 318 ms 26232 KB Output is correct
4 Correct 354 ms 27072 KB Output is correct
5 Correct 337 ms 26436 KB Output is correct
6 Correct 357 ms 26752 KB Output is correct
7 Correct 359 ms 27064 KB Output is correct
8 Correct 323 ms 27248 KB Output is correct
9 Correct 166 ms 26388 KB Output is correct
10 Correct 322 ms 26928 KB Output is correct
11 Correct 396 ms 26624 KB Output is correct
12 Correct 319 ms 26400 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 326 ms 25824 KB Output is correct
3 Correct 305 ms 25920 KB Output is correct
4 Correct 317 ms 25836 KB Output is correct
5 Correct 331 ms 26220 KB Output is correct
6 Correct 316 ms 25640 KB Output is correct
7 Correct 358 ms 26228 KB Output is correct
8 Correct 310 ms 29388 KB Output is correct
9 Correct 332 ms 29188 KB Output is correct
10 Correct 369 ms 29044 KB Output is correct
11 Incorrect 343 ms 29176 KB Output isn't correct
12 Halted 0 ms 0 KB -