제출 #576856

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
576856		wiwiho	Event Hopping (BOI22_events)	C++14	0 / 100	1590 ms	1916 KiB

events

#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define pob pop_back()
#define ef emplace_front
#define pof pop_front()
#define mp make_pair
#define F first
#define S second
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;

    vector<int> l(n + 1), r(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> l[i] >> r[i];
    }

    vector<int> a(n + 1);
    iota(iter(a), 0);
    sort(a.begin() + 1, a.end(), [&](int x, int y){ return r[x] < r[y]; });
    vector<int> id(n + 1);
    for(int i = 1; i <= n; i++){
        id[a[i]] = i;
    }

    while(q--){

        int s, e;
        cin >> s >> e;
        //cerr << "query " << s << " " << e << "\n";
        
        if(s == e){
            cout << "0\n";
            continue;
        }
        if(r[s] > r[e]){
            cout << "impossible\n";
            continue;
        }
    
        int now = id[e];
        int tl = l[e];
        int ans = 0;
        //cerr << "test " << tl << "\n";
        while(r[s] < tl){
            if(r[a[now - 1]] < tl) break;
            int owo = tl;
            while(tl <= r[a[now - 1]]){
                owo = min(owo, l[a[now - 1]]);
                now--;
            }
            tl = owo;
            //cerr << "test " << tl << "\n";
            ans++;
        }
        if(r[s] < tl) cout << "impossible\n";
        else cout << ans + 1 << "\n";

    }

    
    return 0;
}

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