oj.uz

Submission #576856

# Submission time Handle Problem Language Result Execution time Memory
576856 2022-06-13T16:30:24 Z wiwiho Event Hopping (BOI22_events) C++14
0 / 100
 1500 ms 1916 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1590 ms 1916 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1586 ms 1892 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1590 ms 1916 KB Time limit exceeded
3 Halted 0 ms 0 KB -