oj.uz

Submission #745986

# Submission time Handle Problem Language Result Execution time Memory
745986 2023-05-21T10:24:36 Z vjudge1 Event Hopping (BOI22_events) C++11
0 / 100
 178 ms 9152 KB 
#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) && (it!=g.end()) && (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;
}

/*
7 7
1 4
5 7
3 5
7 9
10 12
12 13
13 16
1 4
1 2
4 1
2 1
1 6
5 6
6 7
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 3776 KB Output is correct
2 Correct 162 ms 4088 KB Output is correct
3 Correct 159 ms 3948 KB Output is correct
4 Incorrect 178 ms 9152 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -