제출 #862343

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
862343		TAhmed33	Osumnjičeni (COCI21_osumnjiceni)	C++98	0 / 110	110 ms	72016 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 = 2e6 + 25;
struct SegmentTree {
	int tree[MAXN2], lazy[MAXN2];
	int tl[MAXN2], tr[MAXN2];
	int cnt = 1;
	void init () {
		for (int i = 1; i < MAXN2; i++) {
			tl[i] = tr[i] = lazy[i] = -1;
		}
	}
	void ext (int node) {
		if (tl[node] == -1) tl[node] = ++cnt;
		if (tr[node] == -1) tr[node] = ++cnt;
	}
	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;
		}
		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];
		return min(get(l, mid, a, b, tl[node]), get(mid + 1, r, a, b, tr[node]));
	}
} cur;
pair <int, int> arr[MAXN];
int nxt[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;
	arr[n + 1].first = 1; arr[n + 1].second = 1e9;
	cur.init(); cur.update(1, MAXL, -MAXL, MAXL, n + 1, 1);
	for (int i = n; i >= 1; i--) {
		nxt[i] = cur.get(1, MAXL, arr[i].first, arr[i].second, 1);
		cur.update(1, MAXL, arr[i].first, arr[i].second, i, 1);
	}
	int q;
	cin >> q;
	while (q--) {
		int l, r;
		cin >> l >> r;
		int dp[n + 1] = {};
		for (int i = r; i >= l; i--) {
			if (nxt[i] > r) {
				dp[i] = 1;
			} else {
				dp[i] = 1 + dp[nxt[i]];
			}
		}
		cout << dp[l] << '\n';
	}
}

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