제출 #1144236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144236		nasir_bashirov	Osumnjičeni (COCI21_osumnjiceni)	C++20	0 / 110	1103 ms	254052 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<int> t[2][sz * 8];
set<int> st;
map<int, int> mp;

void update(int ver, int i, int v, int x, int lx, int rx){
	t[ver][x].insert(v);
	if(lx == rx){
		return;
	}
	int mid = (lx + rx) / 2;
	if(i <= mid)	update(ver, i, v, x * 2, lx, mid);
	else	update(ver, i, v, x * 2 + 1, mid + 1, rx);
}

int query(int ver, int l, int r, int ind, int x, int lx, int rx){
	if(lx >= l and rx <= r){
		auto it = t[ver][x].lower_bound(ind);
		if(it != t[ver][x].end()){
			return *it;
		}
		return 1e9;
	}
	if(l > rx or lx > r)	return 1e9;
	int mid = (lx + rx) / 2;
	return min(query(ver, l, r, ind, x * 2, lx, mid), query(ver, l, r, ind, x * 2 + 1, mid + 1, rx));
}

/*
	{l[i], r[i]} sort edirik
	1, 2, ... n for atib [l[i], n] intrevalina baxiriq
	{r[i], l[i]} sort edirik
	1, 2, ... n for atib [l[i], n] intervalina baxiriq
*/

void fmain(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> l[i] >> r[i];
		st.insert(l[i]);
		st.insert(r[i]);
	}
	for(int i : st){
		mp[i] = ++p;
	}
	for(int i = 1; i <= n; i++)	l[i] = mp[l[i]], r[i] = mp[r[i]];
	for(int i = 0; i < lg; i++){
		for(int j = 1; j <= n + 1; j++)	dp[j][i] = n + 1;
	}
	vector<pair<pii, int>> v;
	for(int i = 1; i <= n; i++){
		v.push_back({{l[i], r[i]}, -i});
	}
	sort(all(v));
	for(int i = 0; i < n; i++){
		v[i].second *= -1;
		dp[v[i].second][0] = min(dp[v[i].second][0], query(0, v[i].first.first, p, v[i].second, 1, 1, p));
		update(0, v[i].first.second, v[i].second, 1, 1, p);
	}
	v.clear();
	for(int i = 1; i <= n; i++){
		v.push_back({{-r[i], -l[i]}, -i});
	}
	sort(all(v));
	for(int i = 0; i < n; i++){
		v[i].second *= -1, v[i].first.first *= -1, v[i].first.second *= -1;
		dp[v[i].second][0] = min(dp[v[i].second][0], query(1, 1, v[i].first.first, v[i].second, 1, 1, p));
		update(1, v[i].first.second, v[i].second, 1, 1, p);
	}
	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: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 50