oj.uz

Submission #595628

# Submission time Handle Problem Language Result Execution time Memory
595628 2022-07-13T22:13:55 Z definitelynotmee Event Hopping (BOI22_events) C++
30 / 100
 113 ms 11332 KB 
#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
const int INF = 1<<30;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n, q;
    cin >> n >> q;
    vector<pii> v(n);
    for(pii& i : v){
        cin >> i.ff >> i.ss;
        i.ff = INF-i.ff;
        i.ss = INF-i.ss;
        swap(i.ff,i.ss);
    }
    // cout << "----------\n";
    // for(pii i : v)
    //     cout << i.ff << ' ' << i.ss << '\n';
    // cout << "----------\n";
    vector<int>o(n);
    iota(all(o),0);
    sort(all(o),[&](int a, int b){
        return v[a] > v[b];
    });

    vector<int> jmp(n);
    vector<int> st;

    for(int i : o){
        int ini = 0, fim = st.size();
        while(ini!=fim){
            int m = (ini+fim)>>1;
            if(v[st[m]].ff <= v[i].ss)
                fim = m;
            else ini = m+1;
        }
        if(ini == st.size()){
            jmp[i] = i;
        } else jmp[i] = st[ini];
        
        while(!st.empty() && v[st.back()].ss <= v[i].ss)
            st.pop_back();
        if(st.empty() || v[st.back()].ff > v[i].ff)
            st.push_back(i);
        // cout << i << ":\n";
        // for(int i : st)
        //     cout << i << ' ';
        // cout << '\n';
    }

    matrix<int> lift(20,vector<int>(n));
    for(int i = 0; i < n; i++){
        lift[0][i] = jmp[i]; 
        // cout << jmp[i] << ' ';
    }
    // cout << '\n';
    for(int i = 1; i < 20; i++){
        for(int j = 0; j < n; j++){
            lift[i][j] = lift[i-1][lift[i-1][j]];
        }
    }
    
    while(q--){
        int a, b;
        cin >> a >> b;
        a--, b--;
        swap(a,b);
        if(v[a] > v[b]){
            cout << "impossible\n";
            continue;
        }
        if(a == b){
            cout << 0 << '\n';
            continue;
        }
        if(v[a].ss >= v[b].ff){
            cout << 1 << '\n';
            continue;
        }
        int ct = 2;
        for(int i = 19; i >= 0; i--){
            if(v[lift[i][a]].ss < v[b].ff)
                ct+=1<<i, a = lift[i][a];
        }
        a = lift[0][a];
        if(v[a].ss >= v[b].ff){
            cout << ct << '\n';
        } else {
            cout << "impossible\n";
        }
    }

}

Compilation message

events.cpp: In function 'int main()':
events.cpp:46:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         if(ini == st.size()){
      |            ~~~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 63 ms 10836 KB Output is correct
3 Correct 87 ms 10860 KB Output is correct
4 Correct 106 ms 10796 KB Output is correct
5 Correct 85 ms 10820 KB Output is correct
6 Correct 82 ms 10984 KB Output is correct
7 Correct 86 ms 10820 KB Output is correct
8 Correct 92 ms 11304 KB Output is correct
9 Correct 94 ms 11260 KB Output is correct
10 Correct 81 ms 11204 KB Output is correct
11 Incorrect 90 ms 11092 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 31 ms 1272 KB Output is correct
20 Correct 36 ms 1236 KB Output is correct
21 Correct 30 ms 1604 KB Output is correct
22 Incorrect 24 ms 1620 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 39 ms 10580 KB Output is correct
20 Correct 35 ms 10592 KB Output is correct
21 Correct 36 ms 10064 KB Output is correct
22 Incorrect 37 ms 10448 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 10760 KB Output is correct
2 Correct 76 ms 10900 KB Output is correct
3 Correct 111 ms 10808 KB Output is correct
4 Correct 113 ms 11332 KB Output is correct
5 Correct 94 ms 11184 KB Output is correct
6 Correct 82 ms 10916 KB Output is correct
7 Correct 81 ms 10996 KB Output is correct
8 Correct 70 ms 11052 KB Output is correct
9 Correct 42 ms 10564 KB Output is correct
10 Correct 77 ms 10580 KB Output is correct
11 Correct 73 ms 10580 KB Output is correct
12 Correct 74 ms 10584 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 63 ms 10836 KB Output is correct
3 Correct 87 ms 10860 KB Output is correct
4 Correct 106 ms 10796 KB Output is correct
5 Correct 85 ms 10820 KB Output is correct
6 Correct 82 ms 10984 KB Output is correct
7 Correct 86 ms 10820 KB Output is correct
8 Correct 92 ms 11304 KB Output is correct
9 Correct 94 ms 11260 KB Output is correct
10 Correct 81 ms 11204 KB Output is correct
11 Incorrect 90 ms 11092 KB Output isn't correct
12 Halted 0 ms 0 KB -