oj.uz

Submission #855890

# Submission time Handle Problem Language Result Execution time Memory
855890 2023-10-02T06:54:34 Z NotLinux Osumnjičeni (COCI21_osumnjiceni) C++17
0 / 110
 81 ms 22484 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 21076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 22484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 21076 KB Output isn't correct
2 Halted 0 ms 0 KB -