Submission #1029430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029430		hasan2006	Event Hopping (BOI22_events)	C++17	30 / 100	378 ms	79808 KiB

events

#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 5e5 + 9 , mod = 1e9 + 7;
ll  dp[N] , a[N] ,c[N] ,  b[N] , p[N][22], A[N] , B[N];
vector<int>vc[N];
void solve()
{
    ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
    cin>>n>>m;
    set<int>sk , ss ,st;
    map<int,int>mp;
    vector<pair<ll,ll>>v;
    for(i = 1; i <= n; i++){
        cin>>a[i]>>b[i];
        ss.insert(a[i]);
        ss.insert(b[i]);
    }
    for(auto it : ss)
        mp[it] = ++s;
    for(i = 1; i <= n; i++){
        a[i] = mp[a[i]] , b[i] = mp[b[i]];
        v.pb({a[i] , b[i]});
        st.insert(b[i]);
    }
    sort(all(v));
    for(auto to : v){
        while(st.size() && *st.begin() < to.fi)
            p[*st.begin()][0] =  mx , st.erase(st.begin());

        mx = max(mx , to.se);
    }
    for(auto it : st)
        p[it][0] = mx;
    ss.clear() , st.clear();
    for(i = s; i >= 1; i--)
        for(j = 1; j <= 20; j++)
            p[i][j] = p[p[i][j - 1]][j - 1];
   for(j = 1; j <= m; j++){
        cin>>A[j]>>B[j];
        l = A[j] , r = B[j];
        if(b[l] > b[r]){
           // cout<<"impossible\n";
            continue;
        }
        if(b[l] >= a[r] && b[l] <= b[r]){
            //cout<<(l != r)<<"\n";
            continue;
        }
        l = b[l];
        s = 0;
        for(i = 20; i >= 0; i--)
            if(p[l][i] && p[l][i] < a[r])
                s += (1 << i) , l = p[l][i];
        if(p[l][0] >= a[r]){
            vc[l].pb(j);
            //cout<<s + 2<<"\n";
        }else {
            //cout<<"impossible\n";
        }
    }
    for(i = 1; i <= n; i++)
        st.insert(b[i]);
    for(auto to : v){
        while(st.size() && *st.begin() < to.fi){
            for(auto to : vc[*st.begin()]){
                l = a[B[to]] , r = b[B[to]];
                auto it = ss.lower_bound(l);
                c[to] = (it != ss.end() && l <= *it && *it <= r);
            }
            st.erase(st.begin());

        }
        ss.insert(to.se);
    }
    for(auto it : st){
        for(auto to : vc[it]){
                l = a[B[to]] , r = b[B[to]];
                auto it1 = ss.lower_bound(l);
                c[to] = (it1 != ss.end() && l <= *it1 && *it1 <= r);
            }
    }

    for(j = 1; j <= m; j++){
    l = A[j] , r = B[j];
        if(b[l] > b[r]){
            cout<<"impossible\n";
            continue;
        }
        if(b[l] >= a[r] && b[l] <= b[r]){
            cout<<(l != r)<<"\n";
            continue;
        }
        l = b[l];
        s = 0;
        for(i = 20; i >= 0; i--)
            if(p[l][i] && p[l][i] < a[r])
                s += (1 << i) , l = p[l][i];
        if(p[l][0] >= a[r] && c[j]){
            cout<<s + 2<<"\n";
        }else {
            cout<<"impossible\n";
        }
    }

}


int main(){
    TL;
    /*#ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif*/
    int t = 1;
//    cin>>t;
    while(t--)
     {
        solve();
     }
}
// Author : حسن

Compilation message (stderr)

events.cpp: In function 'void solve()':
events.cpp:26:12: warning: unused variable 'q' [-Wunused-variable]
   26 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |            ^
events.cpp:26:30: warning: unused variable 'x' [-Wunused-variable]
   26 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                              ^
events.cpp:26:34: warning: unused variable 'y' [-Wunused-variable]
   26 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                  ^
events.cpp:26:46: warning: unused variable 'f' [-Wunused-variable]
   26 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                              ^
events.cpp:26:50: warning: unused variable 'k' [-Wunused-variable]
   26 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                  ^
events.cpp:26:58: warning: unused variable 'mn' [-Wunused-variable]
   26 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                          ^~

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