Submission #1031405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031405		hasan2006	Event Hopping (BOI22_events)	C++17	100 / 100	78 ms	26816 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 a[N] , b[N] , dp[N] , c[N] , d[N] , p[N][20]  , S[N] , E[N] ;

void solve()
{
    ll n ,t , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
	cin>>n>>q;
	vector<pair<ll,pair<ll,ll>>>v;
	for(i = 0; i < n; i++){
        cin>>x>>y;
        v.pb({y , {x , i}});
	}
	sort(all(v));
	for(i = 0; i < n; i++)
		c[v[i].se.se] = i;
	for(i = 0; i < n; i++)
		S[i] = v[i].se.fi , E[i] = v[i].fi;
	for (i = 0; i < n; i++)
		S[i] = (lower_bound(E, E + n, S[i]) - E);
	vector<ll>V;
	for(j = 0; j < n; j++){
		if(S[j] >= j)
			p[j][0] = j;
		else{
			auto it = lower_bound(V.begin(), V.end(), S[j]);
			assert(it != V.end());
			p[j][0] = *it;
		}
		for(i = 1; i < 20; i++)
			p[j][i] = p[p[j][i - 1]][i - 1];
		while (!V.empty() && S[V.back()] >= S[j])
			V.pop_back();
		V.push_back(j);
	}
	while(q--){
		cin>>s>>t;
		s = c[s - 1] , t = c[t - 1];
		if(s == t)
			cout<<0<<"\n";
		else {
			if(v[t].se.fi <= v[s].fi && v[s].fi <= v[t].fi)
				cout<<1<< "\n";
			else{
				if(s >= t){
					cout<<"impossible\n";
					continue;
				}
				x = 1;
				for(i = 19; i >= 0; i--)
					if(s < S[p[t][i]])
						t = p[t][i] , x += (1 << i);
				if(s < S[t])
					t = p[t][0] , x++;
				if(s >= S[t])
					cout<<x<<"\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:26: warning: unused variable 'l' [-Wunused-variable]
   26 |     ll n ,t , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                          ^
events.cpp:26:29: warning: unused variable 'r' [-Wunused-variable]
   26 |     ll n ,t , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                             ^
events.cpp:26:49: warning: unused variable 'f' [-Wunused-variable]
   26 |     ll n ,t , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                                                 ^
events.cpp:26:53: warning: unused variable 'k' [-Wunused-variable]
   26 |     ll n ,t , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                                                     ^
events.cpp:26:57: warning: unused variable 'm' [-Wunused-variable]
   26 |     ll n ,t , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                                                         ^
events.cpp:26:61: warning: unused variable 'mx' [-Wunused-variable]
   26 |     ll n ,t , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                                                             ^~
events.cpp:26:70: warning: unused variable 'mn' [-Wunused-variable]
   26 |     ll n ,t , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
      |                                                                      ^~

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