oj.uz

Submission #1031404

# Submission time Handle Problem Language Result Execution time Memory
1031404 2024-07-22T19:50:20 Z hasan2006 Event Hopping (BOI22_events) C++17
0 / 100
 559 ms 524288 KB 
#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

events.cpp:88:11: warning: extra tokens at end of #endif directive [-Wendif-labels]
   88 |     #endif*/
      |           ^
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;
      |                                                                      ^~
events.cpp: In function 'int main()':
events.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 497 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 557 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 557 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 557 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 559 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 497 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -