oj.uz

Submission #927056

# Submission time Handle Problem Language Result Execution time Memory
927056 2024-02-14T07:46:46 Z berr Event Hopping (BOI22_events) C++17
0 / 100
 70 ms 23504 KB 
//≽^•⩊•^≼
 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
 
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, q; cin >> n >> q;
 
    vector<array<int, 2>> v(n);
    vector<vector<array<int, 2>>> qu(n);
    vector<array<int, 20>> gh(n);
    vector<int> id(n), ans(q, -1);
 
    for(auto &[i, l]: v) cin >> i >> l;
 
    iota(id.begin(), id.end(), 0);
    
    sort(id.begin(), id.end(), [&](int i, int j){
        return v[i] < v[j];
    });
    
    vector<int> el;
    
     for(int i=0; i<20; i++){
        for(int l=0; l<n; l++){
            gh[l][i]=-1;
        }
    }

 
    for(int i=0; i<n; i++){
    /*   for(auto i: el) cout<<v[i][0]<<" "<<v[i][1]<<"\n";
            cout<<"\n";*/
        if(el.size()){
            int s=-1;
            
            for(int j=17; j>=0; j--){
                int tmp = (s+(1<<j));
                if(tmp >= el.size()) continue;
                if(v[el[tmp]][1]<v[id[i]][0]) s=tmp;
            }
 
            s++;
            if(s<el.size() && v[el[s]][1]>=v[id[i]][0]&&v[el[s]][1]<=v[id[i]][1]){
                gh[id[i]][0]=el[s];
            }
 
        }
 
        if(el.size() && v[el.back()][1]<=v[id[i]][1]){
            while(el.size()&&v[el.back()][0]==v[id[i]][0])el.pop_back();
            el.push_back(id[i]);
        }
        else if(!el.size())el.push_back(id[i]);
    }
    el.clear();

    for(int i=1; i<20; i++){
        for(int l=0; l<n; l++){
            if(gh[l][i-1]==-1) gh[l][i]=-1;
            else gh[l][i] = gh[gh[l][i-1]][i-1];
      
        }
    }   
    
    auto c = [&](int x, int y){
        return !(v[y][1] <= v[x][1]&&v[y][1]>=v[x][0])&&v[x][0]>=v[y][0];
    };
    auto a = [&](int x, int y){
        if(v[x][0]==v[y][0]) return v[y][1] > v[x][1];
        return v[x][0] > v[y][0];

       // return !(v[y][1] <= v[x][1]&&v[y][1]>=v[x][0]);
    };
    auto func =[&](int x, int y)->int{
        int h=0;
        if(x==y) return 0;
       // cout<<x<<" "<<gh[x][0];
        for(int j=9; j>=0; j--){
 
            if(gh[x][j]!=-1&&c(gh[x][j], y)&&(j==0||gh[x][j]!=gh[x][j-1])&& a(x, gh[x][j])){
                h+=(1<<j); x=gh[x][j];
                //j++;
            }

        }

        if(x!=gh[x][0]&&gh[x][0]!=-1)x = gh[x][0], h++;
       // cout<<v[x][1]<<" "<<v[y][1]<<"\n";
        if((v[y][1] <= v[x][1]&&v[y][1]>=v[x][0])) return h+(x==y?0:1);
        return -1LL;
    };
 

 
    while(q--){
        int x, y; cin >> x >> y;
        x--; y--;
        int h = func(y, x);
        if(h==-1) cout<<"impossible";
        else cout<<h;
        cout<<"\n";        
    }


}

Compilation message

events.cpp: In function 'int main()':
events.cpp:45:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |                 if(tmp >= el.size()) continue;
      |                    ~~~~^~~~~~~~~~~~
events.cpp:50:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             if(s<el.size() && v[el[s]][1]>=v[id[i]][0]&&v[el[s]][1]<=v[id[i]][1]){
      |                ~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 70 ms 23404 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 70 ms 23404 KB Output isn't correct
3 Halted 0 ms 0 KB -