Submission #886060

#	Time	Username	Problem	Language	Result	Execution time	Memory
886060		vjudge1	Curtains (NOI23_curtains)	C++17	100 / 100	1447 ms	20164 KiB

curtains

#include <bits/stdc++.h>
using namespace std;
#define tol(bi) (1LL<<((int)(bi)))
typedef long long ll;
constexpr int MOD = 1e9+7;
constexpr int MAXS = 2000005;
constexpr int MAXN = 500002;
int segtree[MAXS]={};
struct SegTree{
	SegTree(int n){/*nothin'*/}
	void dallan(int node){
		if (node*2+2<MAXS){
			segtree[node*2+1]=max(segtree[node*2+1],segtree[node]);
			segtree[node*2+2]=max(segtree[node*2+2],segtree[node]);
		}
	}
	void update(int tarl, int tarr, int val, int l = 0, int r = MAXN, int node = 0){
		dallan(node);
		if (l>=tarl && r<=tarr){
			segtree[node]=max(segtree[node],val);
			dallan(node);
			return;
		}
		int mid = l+(r-l)/2;
		if (mid>=tarl) update(tarl, tarr, val, l, mid, node*2+1);
		if (mid+1<=tarr) update(tarl, tarr, val, mid+1, r, node*2+2);
		segtree[node]=min(segtree[node*2+1],segtree[node*2+2]);
	}
	int query(int tarl, int tarr, int l = 0, int r = MAXN, int node = 0){
		dallan(node);
		if (l>=tarl && r<=tarr) return segtree[node];
		int mid = l+(r-l)/2;
		int lnode = MOD, rnode = MOD;
		if (mid>=tarl) lnode = query(tarl, tarr, l, mid, node*2+1);
		if (mid+1<=tarr) rnode = query(tarl, tarr, mid+1, r, node*2+2);
		return min(lnode, rnode);
	}
};
int main(){
	memset(segtree,-1,sizeof(segtree));
	int n,m,q;
	cin>>n>>m>>q;
	SegTree segtree(n);
	vector<pair<int,int>> arr(m);
	for (int i = 0; i < m; ++i)
	{
		cin>>arr[i].first>>arr[i].second;
	}
	sort(arr.begin(), arr.end(), [&](pair<int,int> a, pair<int,int> b){
		return a.second<b.second;
	});
	int ind = 0;
	vector<array<int,3>> qarr(q);
	vector<bool> ansarr(q,false);
	for (int i = 0; i < q; ++i)
	{
		cin>>qarr[i][0]>>qarr[i][1];
		qarr[i][2]=i;
	}
	sort(qarr.begin(), qarr.end(), [&](array<int,3> a, array<int,3> b){
		return a[1]<b[1];
	});
	for (int i = 0; i < q; ++i)
	{
		while (ind<m && arr[ind].second<=qarr[i][1]){
			segtree.update(arr[ind].first-1,arr[ind].second-1,arr[ind].first-1);
			ind++;
		}
		if (segtree.query(qarr[i][0]-1,qarr[i][1]-1)>=qarr[i][0]-1) ansarr[qarr[i][2]]=true;
	}
	for (int i = 0; i < q; ++i)
	{
		if (ansarr[i]) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}

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