Submission #886040

#	Time	Username	Problem	Language	Result	Execution time	Memory
886040		vjudge1	Curtains (NOI23_curtains)	C++17	80 / 100	1541 ms	29172 KiB

curtains

#include <bits/stdc++.h>
using namespace std;
#define tol(bi) (1LL<<((int)(bi)))
typedef long long ll;
constexpr int MOD = 1e9+7;
struct SegTree{
	vector<int> segtree;
	SegTree(int n){
		segtree.resize(tol(ceil(log2(n)+1))-1,-1);
	}
	void dallan(int node){
		if (node*2+1<segtree.size()){
			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 = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		dallan(node);
		if (l>=tarl && r<=tarr){
			segtree[node]=max(segtree[node],val);
			dallan(node);
			return;
		}
		if (l>tarr || r<tarl) return;
		int mid = l+(r-l)/2;
		update(tarl, tarr, val, l, mid, node*2+1);
		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 = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		dallan(node);
		if (l>=tarl && r<=tarr) return segtree[node];
		if (l>tarr || r<tarl) return MOD;
		int mid = l+(r-l)/2;
		int lnode = query(tarl, tarr, l, mid, node*2+1);
		int rnode = query(tarl, tarr, mid+1, r, node*2+2);
		return min(lnode, rnode);
	}
};
int main(){
	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;
	}
}

Compilation message (stderr)

curtains.cpp: In member function 'void SegTree::dallan(int)':
curtains.cpp:12:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |   if (node*2+1<segtree.size()){
      |       ~~~~~~~~^~~~~~~~~~~~~~~

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