oj.uz

Submission #595631

# Submission time Handle Problem Language Result Execution time Memory
595631 2022-07-13T22:22:45 Z definitelynotmee Event Hopping (BOI22_events) C++
20 / 100
 109 ms 11348 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(v[a] == v[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 10824 KB Output is correct
3 Correct 75 ms 10824 KB Output is correct
4 Correct 109 ms 10780 KB Output is correct
5 Correct 88 ms 10820 KB Output is correct
6 Correct 85 ms 10844 KB Output is correct
7 Correct 84 ms 10824 KB Output is correct
8 Correct 90 ms 11292 KB Output is correct
9 Correct 100 ms 11332 KB Output is correct
10 Correct 91 ms 11220 KB Output is correct
11 Incorrect 82 ms 11004 KB Output isn't correct
12 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 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 Incorrect 1 ms 340 KB Output isn't correct
10 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 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 Incorrect 1 ms 340 KB Output isn't correct
10 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 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 Incorrect 1 ms 340 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 10828 KB Output is correct
2 Correct 77 ms 10780 KB Output is correct
3 Correct 107 ms 10804 KB Output is correct
4 Correct 96 ms 11348 KB Output is correct
5 Correct 106 ms 11204 KB Output is correct
6 Correct 77 ms 10968 KB Output is correct
7 Correct 78 ms 10960 KB Output is correct
8 Correct 76 ms 11064 KB Output is correct
9 Correct 35 ms 10600 KB Output is correct
10 Correct 77 ms 10576 KB Output is correct
11 Correct 72 ms 10576 KB Output is correct
12 Correct 78 ms 10656 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 10824 KB Output is correct
3 Correct 75 ms 10824 KB Output is correct
4 Correct 109 ms 10780 KB Output is correct
5 Correct 88 ms 10820 KB Output is correct
6 Correct 85 ms 10844 KB Output is correct
7 Correct 84 ms 10824 KB Output is correct
8 Correct 90 ms 11292 KB Output is correct
9 Correct 100 ms 11332 KB Output is correct
10 Correct 91 ms 11220 KB Output is correct
11 Incorrect 82 ms 11004 KB Output isn't correct
12 Halted 0 ms 0 KB -