Submission #886133

#	Time	Username	Problem	Language	Result	Execution time	Memory
886133		vjudge1	Curtains (NOI23_curtains)	C++17	0 / 100	1 ms	348 KiB

curtains

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

#define ll long long
#define endl "\n"
#define all(aa) aa.begin(), aa.end()

struct SegmentTree{
	int N;
	vector<int> st, lazy, arr;

	SegmentTree(int N, int val=0): N(N), arr(N, val), st(4*N), lazy(4*N){
		build(1, 0, N-1);
	}

	int build(int n, int s, int e){
		if(s==e) return st[n]=arr[s];
		int mid=(s+e)/2;
		return st[n]=build(n*2, s, mid)+build(n*2+1, mid+1, e);
	}

	void push(int n){
		st[n*2]+=lazy[n]; st[n*2+1]+=lazy[n];
		lazy[n*2]+=lazy[n]; lazy[n*2+1]+=lazy[n];
		lazy[n]=0;
	}

	void update(int n, int s, int e, int l, int r, int val){
		if(s>=l && e<=r){
			lazy[n]+=val;
			st[n]+=val;
			return ;
		}
		push(n);

		int mid=(s+e)/2;
		if(mid>=l) update(n*2, s, mid, l, r, val);
		if(mid<r) update(n*2+1, mid+1, e, l, r, val);
		st[n]=min(st[n*2], st[n*2+1]);
	}

	int query(int n, int s, int e, int l, int r){
		if(s>=l && e<=r) return st[n];
		push(n);

		int mid=(s+e)/2, ans=INT_MAX;
		if(mid>=l) ans=min(ans, query(n*2, s, mid, l, r));
		if(mid<r) ans=min(ans, query(n*2+1, mid+1, e, l, r));
		return ans;
	}

	int query(int l, int r){
		return query(1, 0, N-1, l, r);
	}
	void update(int l, int r, int val){
		return update(1, 0, N-1, l, r, val);
	}
};

const int SQRT=700;

int main(){
	int n, m, q;
	cin>>n>>m>>q;

	vector<set<int>> beg(n), end(n); 
	SegmentTree st(n);
	for(int i=0; i<m; i++){
		int a, b;
		cin>>a>>b;
		a--; b--;

		beg[a].insert(b);
		end[b].insert(a);
		st.update(a, b, 1);
	}

	priority_queue<array<int, 4>, vector<array<int, 4>>, greater<array<int, 4>>> mo;
	for(int i=0; i<q; i++){
		int l, r;
		cin>>l>>r;
		l--; r--;

		mo.push({l/SQRT, r, l, i});
	}

	int cur_l=0, cur_r=n-1;
	vector<bool> ans(q);
	while(mo.size()){
		auto [block, r, l, ind]=mo.top();

		mo.pop();

		for(int i=cur_l; i<l; i++){
			auto it=upper_bound(all(beg[i]), cur_r);
			if(it!=beg[i].begin()){
				int u=*prev(it);
				st.update(i, u, -1);
			}
		}
		for(int i=cur_r; i>r; i--){
			auto it=lower_bound(all(end[i]), cur_l);
			if(it!=end[i].end()){
				int u=*it;
				st.update(u, i, -1);
			}
		}
		for(int i=cur_l; i>=l; i--){
			auto it=upper_bound(all(beg[i]), r);
			if(it!=beg[i].begin()){
				int u=*prev(it);
				st.update(i, u, 1);
			}
		}
		for(int i=cur_r; i<=r; i++){
			auto it=lower_bound(all(end[i]), l);
			if(it!=end[i].end()){
				int u=*it;
				st.update(u, i, 1);
			}
		}

		ans[ind]=(st.query(l, r)==0);
		cur_l=l; cur_r=r;
	}

	for(int i=0; i<q; i++) cout<<(ans[i] ? "NO":"YES")<<endl;
}

Compilation message (stderr)

curtains.cpp: In constructor 'SegmentTree::SegmentTree(int, int)':
curtains.cpp:10:24: warning: 'SegmentTree::arr' will be initialized after [-Wreorder]
   10 |  vector<int> st, lazy, arr;
      |                        ^~~
curtains.cpp:10:14: warning:   'std::vector<int> SegmentTree::st' [-Wreorder]
   10 |  vector<int> st, lazy, arr;
      |              ^~
curtains.cpp:12:2: warning:   when initialized here [-Wreorder]
   12 |  SegmentTree(int N, int val=0): N(N), arr(N, val), st(4*N), lazy(4*N){
      |  ^~~~~~~~~~~

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