Submission #722563

#	Time	Username	Problem	Language	Result	Execution time	Memory
722563		Itamar	Event Hopping (BOI22_events)	C++14	0 / 100	1573 ms	16824 KiB

events

// 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";
        }*/
        int ans = 0;
        int r = a;
        if (b > a) cout << "impossible" << "\n";
        else {
            while (ans < n && r > b) {
                int rt = r;
                for (int i = a; i >= rt; i--)r = min(r, lii[i]);
                //r = seg->query(a, r).first;
                //a = rt;
                ans++;
            }
            if (ans == n)cout << "impossible";
            else cout << ans;
            cout << "\n";
        }
    }
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:64:11: warning: unused variable 'seg' [-Wunused-variable]
   64 |     node* seg = new node(0, n - 1);
      |           ^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30