Submission #573007

#	Time	Username	Problem	Language	Result	Execution time	Memory
573007		StrawHatWess	Event Hopping (BOI22_events)	C++17	0 / 100	303 ms	7724 KiB

events

#include <bits/stdc++.h>
using namespace std;

typedef vector<int>vi; 
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)

template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int INF=2e9;
const int MX=1e5+10; 



void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
}
/////////////////////////ONLY CLEAN CODES ALLOWED/////////////////////////


int N,Q; 
vi L(MX), R(MX);  

bool cmp(int i, int j){
	if(R[i]!=R[j]) return R[i] < R[j];
	return L[i] > L[j];  
}

int main(){
	IO(); 

	cin>>N>>Q; 

	FOR(i,0,N) cin>>L[i]>>R[i]; 

	vi vec(N); iota(all(vec),0); 
	sort(all(vec),cmp); 

	//for(int x: vec) cout << x << " "; cout << endl;

	unordered_map<int,int>mp; 
	FOR(i,0,N) mp[vec[i]]=i; 

	vi jump(N), jump_val(N); 
	int mnl=INF, mnl_idx; 
	ROF(j,0,N){
		int i=vec[j]; 
		if(mnl<=R[i]){
			jump[i]=jump[mnl_idx]; 
			jump_val[i]=jump_val[mnl_idx]+1; 
		}
		else{
			jump[i]=i; 
			jump_val[i]=0; 
			mnl=INF; 
		}

		if(ckmin(mnl,L[i])) mnl_idx=i; 
	}

	//for(int x: jump) cout << x << " "; cout << endl;

	while(Q--){
		int s,e; cin>>s>>e; s--; e--; 
		//s=mp[s], e=mp[e]; 

		//cout << s << " " << e << endl;

		if(s==e) cout << 0 << endl;
		else if((R[s]>=L[e] && R[s]<=R[e]) || (R[e]>=L[s] && R[e]<=R[s])) cout << 1 << endl;
		else if(jump[s]==jump[e] && jump_val[s]>=jump_val[e]) cout << jump_val[s] - jump_val[e] << endl;
		else cout << "impossible" << endl;
	}
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:57:24: warning: 'mnl_idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |    jump[i]=jump[mnl_idx];
      |                        ^

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