제출 #862351

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
862351		TAhmed33	Osumnjičeni (COCI21_osumnjiceni)	C++98	0 / 110	960 ms	488616 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)
bool intersect (pair <int, int> a, pair <int, int> b) {
	return !(a.second < b.first || b.second < a.first);
}
const int MAXN = 2e5 + 25;
const int MAXL = 1e9 + 25;
const int MAXN2 = 2e7 + 25;
struct SegmentTree {
	vector <int> tree, lazy, tl, tr;
	int cnt = 0;
	void p () {
		tree.push_back(1e9);
		lazy.push_back(1e9);
		tl.push_back(-1);
		tr.push_back(-1);
	}
	void init () {
		p();
	}
	void ext (int node) {
		if (tl[node] == -1) {
			tl[node] = ++cnt; p();
		}
		if (tr[node] == -1) {
			tr[node] = ++cnt;
			p();
		}
	}
	void prop (int l, int r, int node) {
		if (lazy[node] == -1) return;
		if (l != r) {
			ext(node);
			lazy[tl[node]] = lazy[node];
			lazy[tr[node]] = lazy[node];
		}
		tree[node] = lazy[node];
		lazy[node] = -1;
	}
	void update (int l, int r, int a, int b, int c, int node) {
		prop(l, r, node);
		if (l > b || r < a) return;
		if (l >= a && r <= b) {
			lazy[node] = c;
			prop(l, r, node);
			return;
		}
		ext(node);
		update(l, mid, a, b, c, tl[node]);
		update(mid + 1, r, a, b, c, tr[node]);
		tree[node] = min(tree[tl[node]], tree[tr[node]]);
	}
	int get (int l, int r, int a, int b, int node) {
		prop(l, r, node);
		if (l > b || r < a) return 1e9;
		if (l >= a && r <= b) return tree[node];
		int sum = 1e9; if (tl[node] != -1) sum = get(l, mid, a, b, tl[node]);
		if (tr[node] != -1) sum = min(sum, get(mid + 1, r, a, b, tr[node]));
		return sum;
	}
} cur;
pair <int, int> arr[MAXN];
int nxt[MAXN]; 
int sparse[22][MAXN];
int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> arr[i].first >> arr[i].second;
	cur.init(); cur.update(1, MAXL, 1, MAXL, n + 1, 1);
	for (int i = n; i >= 1; i--) {
		nxt[i] = cur.get(1, MAXL, arr[i].first, arr[i].second, 1);
		if (i < n) nxt[i] = min(nxt[i], nxt[i + 1]);
		cur.update(1, MAXL, arr[i].first, arr[i].second, i, 1);
	}
	nxt[n + 1] = n + 1;
	for (int i = 1; i <= n; i++) sparse[0][i] = nxt[i];
	sparse[0][n + 1] = n + 1;
	for (int i = 1; i < 22; i++) {
		for (int j = 1; j <= n; j++) {
			sparse[i][j] = sparse[i - 1][sparse[i - 1][j]];
		}
		sparse[i][n + 1] = n + 1;
	}
	int q;
	cin >> q;
	while (q--) {
		int l, r;
		cin >> l >> r;
		int cnt = 0;
		for (int i = 21; i >= 0; i--) {
			if (sparse[i][l] <= r) {
				cnt += (1 << i);
				l = sparse[i][l];
			}
		}
		cout << cnt + 1 << '\n';
	}
}

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