oj.uz

Submission #926574

# Submission time Handle Problem Language Result Execution time Memory
926574 2024-02-13T10:49:03 Z berr Event Hopping (BOI22_events) C++17
20 / 100
 1500 ms 48328 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<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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 201 ms 44120 KB Output is correct
3 Correct 218 ms 46476 KB Output is correct
4 Correct 229 ms 46532 KB Output is correct
5 Execution timed out 1551 ms 44232 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Execution timed out 1535 ms 604 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Execution timed out 1535 ms 604 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Execution timed out 1535 ms 604 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 44104 KB Output is correct
2 Correct 213 ms 46752 KB Output is correct
3 Correct 229 ms 46596 KB Output is correct
4 Correct 77 ms 32132 KB Output is correct
5 Correct 150 ms 40932 KB Output is correct
6 Correct 182 ms 46916 KB Output is correct
7 Correct 188 ms 48328 KB Output is correct
8 Correct 140 ms 45252 KB Output is correct
9 Correct 72 ms 43212 KB Output is correct
10 Correct 206 ms 47500 KB Output is correct
11 Correct 203 ms 47292 KB Output is correct
12 Correct 203 ms 47912 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 201 ms 44120 KB Output is correct
3 Correct 218 ms 46476 KB Output is correct
4 Correct 229 ms 46532 KB Output is correct
5 Execution timed out 1551 ms 44232 KB Time limit exceeded
6 Halted 0 ms 0 KB -