oj.uz

Submission #926575

# Submission time Handle Problem Language Result Execution time Memory
926575 2024-02-13T10:49:44 Z berr Event Hopping (BOI22_events) C++17
20 / 100
 261 ms 45204 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];
            }
        }
        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 344 KB Output is correct
2 Correct 212 ms 44076 KB Output is correct
3 Correct 202 ms 44572 KB Output is correct
4 Correct 261 ms 44780 KB Output is correct
5 Incorrect 185 ms 42948 KB Output isn't correct
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 Incorrect 1 ms 604 KB Output isn't correct
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 Incorrect 1 ms 604 KB Output isn't correct
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 Incorrect 1 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 43924 KB Output is correct
2 Correct 203 ms 44696 KB Output is correct
3 Correct 244 ms 44964 KB Output is correct
4 Correct 70 ms 30252 KB Output is correct
5 Correct 151 ms 39200 KB Output is correct
6 Correct 196 ms 45204 KB Output is correct
7 Correct 181 ms 45076 KB Output is correct
8 Correct 138 ms 42200 KB Output is correct
9 Correct 72 ms 41148 KB Output is correct
10 Correct 201 ms 44512 KB Output is correct
11 Correct 204 ms 44212 KB Output is correct
12 Correct 203 ms 44512 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 212 ms 44076 KB Output is correct
3 Correct 202 ms 44572 KB Output is correct
4 Correct 261 ms 44780 KB Output is correct
5 Incorrect 185 ms 42948 KB Output isn't correct
6 Halted 0 ms 0 KB -