Submission #1031406

#TimeUsernameProblemLanguageResultExecution timeMemory
1031406hasan2006Event Hopping (BOI22_events)C++17
100 / 100
78 ms28352 KiB
#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 = 1e5 + 9 , mod = 1e9 + 7; ll c[N] , d[N] , p[N][22] , 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;
      |                                                                      ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...