Submission #1279440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279440		AbdullahIshfaq	Curtains (NOI23_curtains)	C++20	100 / 100	847 ms	74268 KiB

curtains

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define MOD 998244353
const int N = 500005;
ll seg[4 * N], n;
void modify_range(ll l, ll r, ll v = 1, ll s = 1, ll e = n + 1)
{
	if (r <= s || e <= l)
	{
		return;
	}
	if (l <= s && e <= r)
	{
		seg[v] = min(seg[v], r - 1);
		return;
	}
	ll mid = (s + e) / 2, lc = 2 * v, rc = 2 * v + 1;
	modify_range(l, r, lc, s, mid);
	modify_range(l, r, rc, mid, e);
	seg[v] = min(seg[v], max(seg[lc], seg[rc]));
	return;
}
ll get_range(ll l, ll r, ll v = 1, ll s = 1, ll e = n + 1)
{
	if (r <= s || e <= l)
	{
		return 1;
	}
	if (l <= s && e <= r)
	{
		return seg[v] <= r - 1;
	}
	ll mid = (s + e) / 2, lc = 2 * v, rc = 2 * v + 1;
	return (get_range(l, r, lc, s, mid) & get_range(l, r, rc, mid, e));
}
void solve()
{
	ll m, q, l, r;
	cin >> n >> m >> q;
	vector<vector<ll>> segments(n + 1);
	vector<vector<pair<ll, ll>>> que(n + 1);
	vector<ll> ans(q);
	for (int i = 0; i < m; i++)
	{
		cin >> l >> r;
		segments[l].push_back(r);
	}
	for (int i = 0; i < q; i++)
	{
		cin >> l >> r;
		que[l].push_back({r, i});
	}
	for (int i = 1; i <= n; i++)
	{
		sort(segments[i].begin(), segments[i].end());
		sort(que[i].begin(), que[i].end());
	}
	for (int i = 0; i <= 4 * n; i++)
	{
		seg[i] = 1e18;
	}
	for (int i = n; i >= 1; i--)
	{
		for (auto j : segments[i])
		{
			modify_range(i, j + 1);
		}
		for (auto j : que[i])
		{
			ans[j.second] = get_range(i, j.first + 1);
		}
	}
	for (int i = 0; i < q; i++)
	{
		if (ans[i])
		{
			cout << "YES" << '\n';
		}
		else
		{
			cout << "NO" << '\n';
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int tests = 1;
	// cin >> tests;
	for (int i = 1; i <= tests; i++)
	{
		solve();
	}
	return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36
• Subtask 6: 20 / 20