제출 #1184766

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184766		elotelo966	Curtains (NOI23_curtains)	C++20	0 / 100	0 ms	524 KiB

curtains

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define OYY LLONG_MAX
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define pb push_back
#define lim 500005

const int mod=1000000007;

int n,m,q,cur_cev;

int curtains[lim][2];

int dizi[lim][2];

int tree[4*lim],lazy[4*lim][2];

bool cev[lim];

vector<pair<int,pair<int,pair<int,int>>>> v;

inline void build(int node,int start,int end){
	if(start==end){
		tree[node]=start-1;
		return ;
	}
	build(node*2,start,mid),build(node*2+1,mid+1,end);
}

inline void merge(int node,int start,int end,int x,int y){
	if(lazy[node][0]==0 || lazy[node][1]<x-1){
		lazy[node][0]=x;
		lazy[node][1]=y;
	}
	else{
		lazy[node][0]=min(lazy[node][0],x);
		lazy[node][1]=y;
	}
}

inline void push(int node,int start,int end){
	if(lazy[node][0]==0)return;
	if(start==end){
		if(tree[node]>=lazy[node][0]-1)tree[node]=lazy[node][1];
	}
	else{
		merge(node*2,start,mid,lazy[node][0],lazy[node][1]);
		merge(node*2+1,mid+1,end,lazy[node][0],lazy[node][1]);
	}
	lazy[node][0]=lazy[node][1]=0;
}

inline void update(int node,int start,int end,int l,int r,int x,int y){
	push(node,start,end);
	if(start>end || start>r || end<l)return ;
	if(start>=l && end<=r){
		lazy[node][0]=x;
		lazy[node][1]=y;
		return ;
	}
	update(node*2,start,mid,l,r,x,y),update(node*2+1,mid+1,end,l,r,x,y);
}

inline void query(int node,int start,int end,int l,int r){
	if(start>end || start>r || end<l || ~cur_cev)return ;
	push(node,start,end);
	//if(l==3)cout<<node<<" "<<start<<" "<<end<<" "<<l<<" "<<r<<" "<<tree[node]<<endl;
	if(start>=l && end<=r){
		cur_cev=tree[node];
		return;
	}
	query(node*2,start,mid,l,r),query(node*2+1,mid+1,end,l,r);
}

inline void debug(int node,int start,int end){
	cout<<node<<" "<<start<<" "<<end<<" "<<tree[node]<<" "<<lazy[node][0]<<" "<<lazy[node][1]<<endl;
	if(start==end){
		return ;
	}
	debug(node*2,start,mid),debug(node*2+1,mid+1,end);
}

int32_t main(){
	faster
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++){
		cin>>curtains[i][0]>>curtains[i][1];
		v.pb({curtains[i][1],{0,{curtains[i][0],i}}});
	}
	
	for(int i=1;i<=q;i++){
		cin>>dizi[i][0]>>dizi[i][1];
		v.pb({dizi[i][1],{1,{dizi[i][0],i}}});
	}
	
	sort(v.begin(),v.end());
	
	build(1,1,n);
	
	for(auto a:v){
		int r=a.fi,kim=a.se.fi,l=a.se.se.fi,ind=a.se.se.se;
		cout<<l<<" "<<r<<" "<<kim<<endl;
		if(kim){
			cur_cev=-1;
			query(1,1,n,l,l);
			if(cur_cev==r)cev[ind]=1;
			else cev[ind]=0;
		}
		else{
			update(1,1,n,1,l,l,r);
		}
		debug(1,1,n);
	}
	
	for(int i=1;i<=q;i++){
		if(cev[i])cout<<"YES"<<'\n';
		else cout<<"NO"<<'\n';
	}
	
	return 0;
}
/*7 8 2
6 6
2 4
5 7
3 4
6 7
4 4
2 4
7 7
4 6
3 7
*/

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