Submission #862584

#	Time	Username	Problem	Language	Result	Execution time	Memory
862584		Mizo_Compiler	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	807 ms	111392 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
#define pb push_back
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
const int N = 2e5+5;
int n, mx[(1 << 20)], a[N], sp[N][18];
multiset<int, greater<>> val[N+N];

void mxupd(int l, int r, int x, int i, int v) {
	if (l == r) {
		mx[x] = v;
		return;
	}
	int m = (l + r) >> 1;
	if (i <= m)mxupd(l, m, x*2+1, i, v);
	else mxupd(m+1, r, x*2+2, i, v);
	mx[x] = max(mx[x*2+1], mx[x*2+2]);
}

int mxget(int li, int ri, int x, int l, int r) {
	if (li > r || ri < l)return 0;
	if (li >= l && ri <= r)return mx[x];
	int m = (li + ri) >> 1;
	return max(mxget(li, m, x*2+1, l, r), mxget(m+1, ri, x*2+2, l, r));
}
int l[N], r[N];
int main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	set<int> st;
	for (int i = 1; i <= n; i++) {
		cin >> l[i] >> r[i];
		val[i].insert(0);
		val[n+i].insert(0);
		st.insert(l[i]), st.insert(r[i]);
	}
	int cur = 1;
	map<int, int> mp;
	for (auto &x : st) {
		mp[x] = cur++;
	}
	for (int i = 1; i <= n; i++) {
		l[i] = mp[l[i]], r[i] = mp[r[i]];
	}
	int cr = n;
	a[n] = n;
	val[l[n]].insert(r[n]);
	mxupd(1, 2*n, 0, l[n], r[n]);
	for (int cl = n-1; cl >= 1; cl--) {
		while (mxget(1, 2*n, 0, 1, r[cl]) >= l[cl]) {
			val[l[cr]].erase(val[l[cr]].find(r[cr]));
			mxupd(1, 2*n, 0, l[cr], *val[l[cr]].begin());
			cr--;
		}
		val[l[cl]].insert(r[cl]);
		mxupd(1, 2*n, 0, l[cl], *val[l[cl]].begin());
		a[cl] = cr;
	}
	for (int i = 1; i <= n; i++) {
		sp[i][0] = a[i];
	}
	for (int j = 1; j < 18; j++) {
		for (int i = 1; i <= n; i++) {
			if (sp[i][j-1] < n)sp[i][j] = sp[sp[i][j-1] + 1][j-1];
			else sp[i][j] = n;
		}
	}
	a[0] = -1;
	int q;
	cin >> q;
	while (q--) {
		int a, b;
		cin >> a >> b;
		int ans = 1;
		for (int i = 17; i >= 0 && a < n; i--) {
			if (sp[a][i] < b) {
				ans += (1 << i);
				a = sp[a][i] + 1;
			}
		}
		cout << ans << "\n";
	}
}

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