Submission #926574

#	Time	Username	Problem	Language	Result	Execution time	Memory
926574		berr	Event Hopping (BOI22_events)	C++17	20 / 100	1551 ms	48328 KiB

events

//≽^•⩊•^≼
 
#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<int>> g(n);
    vector<vector<array<int, 2>>> qu(n);
    vector<array<int, 20>> gh(n);
    vector<int> id(n), root, ans(q, -1), vis(n);

    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][1]==v[j][1])?v[i][0]<v[j][0]:v[i][1]<v[j][1];
    });

    vector<int> el;
    for(int i=n-1; i>=0; i--){

        if(el.size()){
            int s=-1;
            int gh = el.size()-1;
            for(int j=17; j>=0; j--){
                int tmp = (s+(1<<j));
                if(tmp >= el.size()) continue;
                if(v[el[gh-tmp]][0]>v[id[i]][1]) s = tmp;
            }

            s++;

            if(s<el.size() && v[el[gh-s]][0]<=v[id[i]][1]){
                g[el[gh-s]].push_back(id[i]);
            }
            else{
                root.push_back(id[i]);
            }

        }

        else root.push_back(id[i]);

        while(el.size() && v[el.back()][0]>=v[id[i]][0]){

            el.pop_back();
        }

        el.push_back(id[i]);
    }
    el.clear();


    for(int i=0; i<20; i++){
        for(int l=0; l<n; l++){
            gh[l][i]=l;
        }
    }

    for(int i=n-1; i>=0; 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(tmp==
                if(v[el[tmp]][0]>v[id[i]][1]) s=tmp;
            }

                s++;
            if(s<el.size() && v[el[s]][0]<=v[id[i]][1]){
                gh[id[i]][0]=el[s];
            }

        }

        if(el.size() && v[el.back()][0]>=v[id[i]][0]){
            el.push_back(id[i]);
        }
        else el.push_back(id[i]);
    }
    el.clear();
    int cnt = 0;
   
    while(q--){
        int x, y; cin >> x >> y;
        x--; y--;

        if(x==y) ans[cnt++]=0;
        else
        qu[x].push_back({y, cnt++});
    }

    vector<int> s;
    int count=0;
    vector<int> par(n); 
    auto c = [&](int x, int y){
        if(v[x][1]==v[y][1]){
            return v[x][0]<v[y][0];
        }
        return v[x][1]<v[y][1];
    };

    for(int i=1; i<20; i++){
        for(int l=0; l<n; l++){
            gh[l][i] = gh[gh[l][i-1]][i-1];
      
        }
    }   


    auto func =[&](int x, int y){
        int h=0;
        for(int j=19; j>=0; j--){
 
            if(c(gh[x][j], y)&&(j==0||gh[x][j]!=gh[x][j-1])){
                h+=(1<<j); x=gh[x][j];
                j++;
            }
        }
        return h+1;
    };
    auto dfs =[&](int vv, int p, auto&&dfs)->void{
        vis[vv] = 1;
       // cout<<vv<<" "<<count<<"\n";
        for(auto [j, i]: qu[vv]){
            if(!vis[j]) continue;
            ans[i] = func(vv, j);
        }   


        for(auto i: g[vv]){
            dfs(i, vv, dfs);
        }

        vis[vv] = 0;
    };
    for(auto i: root) count=1, dfs(i,i, dfs);
       // cout<<val[4671];
    for(auto j: ans){

        if(j!=-1) cout<<j<<endl;
        else cout<<"impossible\n";
        //else cout<<j-1<<"\n";
    }
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:37: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]
   37 |                 if(tmp >= el.size()) continue;
      |                    ~~~~^~~~~~~~~~~~
events.cpp:43: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]
   43 |             if(s<el.size() && v[el[gh-s]][0]<=v[id[i]][1]){
      |                ~^~~~~~~~~~
events.cpp:78: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]
   78 |                 if(tmp >= el.size()) continue;
      |                    ~~~~^~~~~~~~~~~~
events.cpp:84: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]
   84 |             if(s<el.size() && v[el[s]][0]<=v[id[i]][1]){
      |                ~^~~~~~~~~~
events.cpp:108:9: warning: variable 'count' set but not used [-Wunused-but-set-variable]
  108 |     int count=0;
      |         ^~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30