Submission #855890

#	Time	Username	Problem	Language	Result	Execution time	Memory
855890		NotLinux	Osumnjičeni (COCI21_osumnjiceni)	C++17	0 / 110	81 ms	22484 KiB

Main

#include <bits/stdc++.h>
using namespace std;
void solve(){
	int n;cin >> n;
	int l[n],r[n],lift[n+1][21];
	lift[n][0] = n;
	for(int i = 0;i<n;i++)cin >> l[i] >> r[i];
	set < pair < int , int > > ste;
	int rp = 0;
	for(int lp = 0;lp < n;lp++){
		while(rp != n){
			if(ste.size() == 0){
				ste.insert({l[rp],r[rp]});
				rp++;
			}
			else{
				pair < int , int > cand1 = *(--ste.lower_bound(make_pair(l[rp],1e9 + 7)));
				//cout << "trying : " << lp << " " << rp << " " << cand1.first << " " << cand1.second << endl;
				if(cand1.first > r[rp] or cand1.second < l[rp]){
					ste.insert({l[rp],r[rp]});
					rp++;
					//cout << "succes" << endl;
				}
				else {
					//cout << "failure" << endl;
					break;
				}
			}
		}
		lift[lp][0] = rp;
		ste.extract({l[lp],r[lp]});
		//cout << lp << " " << rp << endl;
	}
	for(int i = 1;i<21;i++){
		for(int j = 0;j<=n;j++){
			lift[j][i] = lift[lift[j][i-1]][i-1];
		}
	}
	int q;cin >> q;
	while(q--){
		int ql,qr;cin >> ql >> qr;ql--;qr--;
		int ans = 0 , cur = ql;
		for(int i = 20;i>=0;i--){
			if(lift[cur][i] <= qr){
				cur = lift[cur][i];
				ans += (1 << i);
			}
		}
		cout << ans+1 << endl;
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 50