oj.uz

Submission #926536

# Submission time Handle Problem Language Result Execution time Memory
926536 2024-02-13T08:32:51 Z berr Event Hopping (BOI22_events) C++17
0 / 100
 77 ms 19872 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<int> id(n), root, val(n), ans(q, -1), vis(n), c(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++;
           // cout<<v[el[s]][0]<<" "<<<v[id[i]][1]<<"\n";
            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]);
    }
    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;
    auto dfs =[&](int vv, int p, auto&&dfs)->void{
        val[vv]=count;
        vis[vv] = 1;
      //  cout<<vv<<" "<<p<<"\n";
        //cerr<<vv<<" "<<count<<"\n";

        for(auto [j, i]: qu[vv]){
            if(!vis[j]) continue;
        //    cerr<<i<<" "<<j<<"gg\n";
            ans[i] = count-val[j];
        //    cout<<p<<"\n";
        //    if(i==0)cout<<count<<"\n";
      //      if(c[j]==0)ans[i]++;
        }   

      //  cerr<<vv<<" "<<count<<"\n";


    //    cout<<endl;
        count++;
        for(auto i: g[vv]){
            //cout<<v[i][1]<<" "<<v[p][0]<<"\n";

                dfs(i, vv, dfs);
                //c[vv] = 0;
               
        }
        count--;
        vis[vv] = 0;
    };
    for(auto i: root) dfs(i, i, dfs);
   //     cout<<endl;

    for(auto j: ans){
        if(j!=-1) cout<<j<<"\n";
        else cout<<"impossible"<<"\n";
        //else cout<<j-1<<"\n";
    }
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:36: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]
   36 |                 if(tmp >= el.size()) continue;
      |                    ~~~~^~~~~~~~~~~~
events.cpp:42: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]
   42 |             if(s<el.size() && v[el[gh-s]][0]<=v[id[i]][1]){
      |                ~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 57 ms 18624 KB Output is correct
3 Correct 64 ms 19100 KB Output is correct
4 Correct 77 ms 19616 KB Output is correct
5 Correct 60 ms 18772 KB Output is correct
6 Correct 58 ms 18260 KB Output is correct
7 Correct 61 ms 18140 KB Output is correct
8 Correct 49 ms 14544 KB Output is correct
9 Correct 50 ms 14668 KB Output is correct
10 Correct 64 ms 18516 KB Output is correct
11 Incorrect 69 ms 17236 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 18628 KB Output is correct
2 Correct 62 ms 19252 KB Output is correct
3 Correct 74 ms 19284 KB Output is correct
4 Correct 49 ms 14668 KB Output is correct
5 Correct 70 ms 18524 KB Output is correct
6 Incorrect 70 ms 19872 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 57 ms 18624 KB Output is correct
3 Correct 64 ms 19100 KB Output is correct
4 Correct 77 ms 19616 KB Output is correct
5 Correct 60 ms 18772 KB Output is correct
6 Correct 58 ms 18260 KB Output is correct
7 Correct 61 ms 18140 KB Output is correct
8 Correct 49 ms 14544 KB Output is correct
9 Correct 50 ms 14668 KB Output is correct
10 Correct 64 ms 18516 KB Output is correct
11 Incorrect 69 ms 17236 KB Output isn't correct
12 Halted 0 ms 0 KB -