제출 #862563

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
862563		Mizo_Compiler	Osumnjičeni (COCI21_osumnjiceni)	C++17	0 / 110	797 ms	85952 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];
struct node {
	int ls, ans;
};
vector<node> t((1 << 19));
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));
}
node nd;
node merge(node x, node y, int ly) {
	return {
		(y.ls == ly && a[x.ls] >= ly ? x.ls : y.ls),
		x.ans + y.ans - (y.ls == ly && a[x.ls] >= ly ? 1 : 0)
	};
}
void build(int li, int ri, int x) {
	if (li == ri) {
		t[x].ans = 1;
		t[x].ls = li;
		return;
	}
	int m = (li + ri) >> 1;
	build(li, m, x*2+1);
	build(m+1, ri, x*2+2);
	t[x] = merge(t[x*2+1], t[x*2+2], m+1);
}

void get(int li, int ri, int x, int l, int r) {
	if (li > r || ri < l)return;
	if (li >= l && ri <= r) {
		nd = merge(nd, t[x], li);
		return;
	}
	int m = (li + ri) >> 1;
	get(li, m, x*2+1, l, r);
	get(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]];
	}
	assert(cur-1 <= 2*n);
	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--;
			assert(cr >= cl);
		}
		val[l[cl]].insert(r[cl]);
		mxupd(1, 2*n, 0, l[cl], *val[l[cl]].begin());
		a[cl] = cr;
		assert(a[cl] <= a[cl+1]);
	}
	build(1, n, 0);
	int q;
	cin >> q;
	while (q--) {
		int a, b;
		cin >> a >> b;
		nd.ans = 0;
		nd.ls = -1;
		get(1, n, 0, a, b);
		cout << nd.ans << "\n";
	}
}

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