Submission #1144244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144244		nasir_bashirov	Osumnjičeni (COCI21_osumnjiceni)	C++20	110 / 110	266 ms	26260 KiB

Main

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define db long double
#define vll vector<pll>
#define F first
#define S second
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

// #define int long long 

const int sz = 2e5 + 5;
const int lg = 19;
int n, q, a, b, l[sz], r[sz], dp[sz][lg], p;
set<pii> st;

bool check(int ind){
	auto it = st.lower_bound({l[ind], 0});
	int x = it -> second;
	if(l[ind] <= l[x] and r[ind] >= l[x])	return false;
	if(it != st.begin()){
		--it;
		int x = it -> second;
		if(l[x] <= l[ind] and r[x] >= l[ind])	return false;
	}
	return true;
}

void fmain(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> l[i] >> r[i];
	}
	for(int i = 0; i < lg; i++){
		for(int j = 1; j <= n + 1; j++)	dp[j][i] = n + 1;
	}
	int p = 0;
	for(int i = 1; i <= n; i++){
		if(p < i){
			st.clear();
			p = i;
			st.insert({l[i], i});
		}
		while(p < n){
			// cout << p << endl;
			if(check(p + 1)){
				p++;
				st.insert({l[p], p});
			}
			else{
				break;
			}
		}
		st.erase({l[i], i});
		dp[i][0] = p + 1;
	}
	for(int i = n; i >= 1; i--){
		dp[i][0] = min(dp[i][0], dp[i + 1][0]);
	}
	for(int i = 1; i < lg; i++){
		for(int j = 1; j <= n; j++){
			dp[j][i] = dp[dp[j][i - 1]][i - 1];
		}
	}
	cin >> q;
	while(q--){
		cin >> a >> b;
		int res = 1;
		for(int i = lg - 1; i >= 0; i--){
			if(dp[a][i] <= b){
				res += (1 << i);
				a = dp[a][i];
			}
		}
		cout << res << endl;
	}
}

signed main(){
	fastio;
	int tmr = 1;
	// cin >> tmr;
	while(tmr--){
		fmain();
	}
	
}

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