Submission #855892

#	Time	Username	Problem	Language	Result	Execution time	Memory
855892		NotLinux	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	420 ms	33668 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){
			//cout << lp << " : ";for(auto itr : ste)cout << itr.first << "," << itr.second << "   ";cout << endl;
			if(ste.size() == 0){
			//	cout << "added " << lp << " " << rp << endl;
				ste.insert({l[rp],r[rp]});
				rp++;
			}
			else{
				auto it = ste.lower_bound(make_pair(l[rp],1e9 + 7));
				pair < int , int > cand1 , cand2;

				if(it == ste.end())cand2 = {-1,-1};
				else cand2 = *it;

				if(it == ste.begin())cand1 = {-1,-1};
				else cand1 = *(--it);

			//	cout << "trying : " << lp << " " << rp << " " << cand1.first << " " << cand1.second << " : " << cand2.first << " " << cand2.second << endl;
				if((cand1.first > r[rp] or cand1.second < l[rp]) and (cand2.first > r[rp] or cand2.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: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 50 / 50