Submission #1265866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265866		namhh	Osumnjičeni (COCI21_osumnjiceni)	C++20	0 / 110	42 ms	15940 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e5+5;
const int lg = 18;
int n,q,st[N][lg];
pii a[N];
set<pii>s;
void build(){
	for(int j = 1; j < lg; j++){
		for(int i = 1; i+(1 << j)-1 <= n; i++) st[i][j] = st[st[i][j-1]][j-1];
	}
}
int jump(int u, int v){
	int sum = 1;
	for(int i = lg-1; i >= 0; i--){
		if(st[u][i] > u && st[u][i] <= v){
			u = st[u][i];
			sum += (1 << i);
		}
	}
	return sum;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se;
	int l = 1;
	int r = 1;
	s.insert({a[1]});
	while(l <= n && r < n){
		auto x = s.lower_bound(make_pair(a[r+1].fi,0));
		if(x != s.end()){
			pii cc = *x;
 			if(cc.fi <= a[r+1].se){
				st[l][0] = r+1;
				s.erase(a[l]);
				l++;
				continue;
			}
		}
		else if(x != s.begin()){
			--x;
			pii cc = *x;
			if(cc.se >= a[r+1].fi){
				st[l][0] = r+1;
				s.erase(a[l]);
				l++;
				continue;
			}
		}
		r++;
		s.insert(a[r]);
	}
	for(int i = l; i <= n; i++) st[i][0] = n+1;
	build();
	cin >> q;
	while(q--){
		int l,r;
		cin >> l >> r;
		cout << jump(l,r) << "\n";
	}
}
//-----+--+----+-==-=*==--=+----------==----------------+=-----==-=+-==----------------
//---===+=----+=----=*=+=*+----------==-----------+=-----==-----==--+-+----------------
//---+=**=-=+---------***+----=------=-------------=-------+-----==-+--=---------------
//----*+-+++**++------=#+----===-----=-------------=-------==-----+-=+=-+--------------
//----++#***+*+++-----=+-----=-=----+---------------+-------+=-----*=-==-+-------------
//---+=+**++**++++==++*=-----===----+---------------+----=---=-----=*+*=-==------------
//---++**==+--++++++***-----+-+-----+---------------==---==--==-----+**---+------------
//----++*#=-+++***+***------+-+-----+----------------=----+---*+=---=*#=-=-+-----------
//-----=**+++*+++**%++-----=--+-----+----------------=----*=--==+==++***-=+==----------
//-------**#**++*%%@==-----=--+-----+-------------=+++++=-+=---+=+=-=+**--+++----------
//---------====+@@%@-=-----+--+--=+++++--------------=----+==--===---+*---+==+---------
//-----------=@*%%%%-=-----+=-==-----=---------------=----+--=-==+-=-=*----++==--------
//----------%#=%=#%%==-----=+--=-----=---------------+----+--===*=*==**=---+-++--------
//--------+@++@=*@%*-=-----=+=-=-----==-------------++-*%%%***=++-+=-+-+---=-===-------
//-------#%-=%=+@%@+-=-----=+=--+++*==*=------------**@*##%*--=-+-----=+---==-+==------
//------=%+-=%=%*@@--=-----=*#*=+*###@%*---------=+*++%***##=-+-+------+---==-=+=------
//-------%*-=%@+@@+-*=-----+-=--@##*##=+==----------=-#*#***-==-+------+---==--++------
//-------+@=+@@*@*-=-=-----=-==-*#%*##=----------------++=+=----+------+---==--==+-----
//--------%@@%%@*=--+=-----=---+=+#==*-------------------==-----+------+---==---=+-----
//----------%+=#-=--==-----+-------===--------------------------*------+---==---+==----
//---------##-%+-=---=-----++----------------------------------=*------=---==---=+=----
//--------=#-*@=-=---=-----**=----------------=----------------+*------=---==----++----
//-------=@==%*-==---=-----++*---------------------------------*+------+---==----++=---
//------=%*-=@--==---=-----+++*-------------------------------**=------+---==----==+---
//------*#--##--==---=-----+++*+--------------------+--------+**=------+---=-----==+---
//-----=@=--@*---=---=-----+++#+*=--------=+=----=+=-------=#+**-------+---+-----==+---
//----=%+--=@+---=---=-----=+**++**=---------------------=*+****------==---+-----===---
//----*#---*@=---=--==-----=*+#++*+++*=---------------=*#*++#+*+==----+==-+=-----====--
//---=@=---%%----=--=+-----=*+#++*++++***+----------*****+++#**++-----+==-+-------===--
//---%#----%%---==--=+------*+*++*++**+***+**++=+****+==++*+**#-+-----+==-+-------+==--
//--=@=---=%#---==--+*------*++*+*++#+*****++++****+--==*=*****==----===-==-------+==--
//--##----=@*---+=--+*------=++*+*++*++++++*******=-------+***==-----===-==-------+==--
//-=@+----+@=---+=--+#=-----=*+*+*++#++*+++**#*++-+-------+***-+-----+===+--------*==--
//-*@=----*@=---=---+*+------++*+*+*-=++*+***=-+--+--------#**-=-----*====--------*==--
//=%%-----#@---==---=**------++****---------*=----+--------=#=+-----=*==*---------*==--
//=@*-----%@---==---=*#------++*+------=+%@##@+==%%+*+==----+==-----+*+-++++=+++*++==--

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