제출 #745978

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
745978		vjudge1	Event Hopping (BOI22_events)	C++11	0 / 100	157 ms	4136 KiB

events

#include <bits/stdc++.h>

using namespace std;

struct event{
    int s,e;
    int id;
};

struct query{
    int a,b;
    int id;
};

int n,q;
event events[100001];
query queries[100001];
int new_id[100001];

bool kis(event a,event b) {
    return((a.e<b.e)||((a.e==b.e)&&(a.s<b.s)));
}

void subtask1() {
    set<int> g; g.clear();
    set<int>::iterator it;
    for (int i=0;i<n-1;i++) {
        if (events[i].e<events[i+1].s) {
            g.insert(i);
        }
    }
    int from, to;
    for (int i=0;i<q;i++) {
        from=queries[i].a;
        to=queries[i].b;
        it=g.lower_bound(new_id[from]);
        if ((new_id[from] > new_id[to]) || ((from!=to) && (new_id[to]>(*it)))) {
            cout << "Impossible" << endl;
        } else {
            cout << new_id[to]-new_id[from] << endl;
        }
    }
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    for (int i=0;i<n;i++) {
        cin >> events[i].s >> events[i].e;
        events[i].id=i+1;
    }
    for (int i=0;i<q;i++) {
        cin >> queries[i].a >> queries[i].b;
        queries[i].id=i;
    }
    sort(events,events+n,kis);
    for (int i=0;i<n;i++) {
        new_id[events[i].id]=i;
    }
    subtask1();

    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