Submission #1246327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246327		PlayVoltz	Osumnjičeni (COCI21_osumnjiceni)	C++20	110 / 110	482 ms	55008 KiB

Main

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
#include <chrono>
#include <fstream>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

set<pii> s;

bool die(pii a){
	if (!s.size())return 0;
	auto it=s.upper_bound(mp(a.fi, -1));
	if (it!=s.end()&&it->fi<=a.se)return 1;
	if (it!=s.begin()){
		--it;
		if (it->se>=a.fi)return 1;
	}
	return 0;
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, q, a, b;
	cin>>n;
	vector<pii> vect(n+1);
	vector<vector<int> > twok(n+1, vector<int>(20, 0));
	for (int i=1; i<=n; ++i)cin>>vect[i].fi>>vect[i].se;
	for (int i=1, p=1; i<=n; ++i){
		while (die(vect[i]))s.erase(vect[p]), ++p;
		twok[i][0]=p-1;
		s.insert(vect[i]);
	}
	for (int j=1; j<20; ++j)for (int i=1; i<=n; ++i)twok[i][j]=twok[twok[i][j-1]][j-1];
	cin>>q;
	while (q--){
		cin>>a>>b;
		int ans=0;
		for (int i=19; i>=0; --i)if (twok[b][i]>=a)b=twok[b][i], ans+=(1<<i);
		cout<<ans+1<<"\n";
	}
}

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