Submission #862356

#	Time	Username	Problem	Language	Result	Execution time	Memory
862356		TAhmed33	Osumnjičeni (COCI21_osumnjiceni)	C++98	110 / 110	394 ms	32276 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 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;
struct SegmentTree {
	int tree[4 * MAXN], lazy[4 * MAXN];
	void init () {
		for (int i = 1; i < 4 * MAXN; i++) lazy[i] = -1;
	}
	void prop (int l, int r, int node) {
		if (lazy[node] == -1) return;
		if (l != r) {
			lazy[tl] = lazy[tr] = 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;
		}
		update(l, mid, a, b, c, tl);
		update(mid + 1, r, a, b, c, tr);
		tree[node] = min(tree[tl], tree[tr]);
	}
	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];
		return min(get(l, mid, a, b, tl), get(mid + 1, r, a, b, tr));
	}
} cur;
pair <int, int> arr[MAXN];
int nxt[MAXN]; 
vector <int> l; 
int sparse[18][MAXN];
int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n; cur.init();
	for (int i = 1; i <= n; i++) cin >> arr[i].first >> arr[i].second;
	for (int i = 1; i <= n; i++) {
		l.push_back(arr[i].first); l.push_back(arr[i].second);
	}
	l.push_back(1); l.push_back((int)1e9);
	sort(l.begin(), l.end()); l.resize(unique(l.begin(), l.end()) - l.begin());
	for (int i = 1; i <= n; i++) {
		arr[i].first = 1 + (lower_bound(l.begin(), l.end(), arr[i].first) - l.begin());
		arr[i].second = 1 + (lower_bound(l.begin(), l.end(), arr[i].second) - l.begin());
	}
	cur.init(); cur.update(1, 400025, 1, 400025, n + 1, 1);
	for (int i = n; i >= 1; i--) {
		nxt[i] = cur.get(1, 400025, arr[i].first, arr[i].second, 1);
		if (i < n) nxt[i] = min(nxt[i], nxt[i + 1]);
		cur.update(1, 400025, arr[i].first, arr[i].second, i, 1);
	}
	nxt[n + 1] = n + 1;
	for (int i = 1; i <= n + 1; i++) {
		sparse[0][i] = nxt[i];
	}
	for (int i = 1; i < 18; i++) {
		for (int j = 1; j <= n + 1; j++) {
			sparse[i][j] = sparse[i - 1][sparse[i - 1][j]];
		}
	}
	int q;
	cin >> q;
	while (q--) {
		int l, r;
		cin >> l >> r;
		int cnt = 0;
		for (int i = 17; i >= 0; i--) {
			if (sparse[i][l] <= r) {
				cnt += (1 << i);
				l = sparse[i][l];
			}
		}
		cout << cnt + 1 << '\n';
	}
}

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