Submission #926535

#	Time	Username	Problem	Language	Result	Execution time	Memory
926535		berr	Event Hopping (BOI22_events)	C++17	0 / 100	79 ms	26028 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<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;
        for(auto i: g[vv]){
            //cout<<v[i][1]<<" "<<v[p][0]<<"\n";
            if(v[i][1]<v[p][0]){
                c[vv] = 1;
                count++;
                dfs(i, vv, dfs);
                c[vv] = 0;
                count--;
            }    
            else{
                c[vv]=0;
                dfs(i, p, dfs);
            }        
        }

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

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

Compilation message (stderr)

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30