Submission #1185389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185389		NotLinux	Curtains (NOI23_curtains)	C++20	100 / 100	809 ms	29816 KiB

curtains

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
const int N = 5e5 + 7;
const int inf = 1e9 + 7;
vector<int>tree(4*N,inf),lazy(4*N,inf);
void push(int ind , int l , int r){
	if(lazy[ind] != inf){
		tree[ind] = min(tree[ind] , lazy[ind]);
		if(l != r){
			lazy[ind*2] = min(lazy[ind*2] , lazy[ind]);
			lazy[ind*2+1] = min(lazy[ind*2+1] , lazy[ind]);
		}
		lazy[ind] = inf;
	}
}
void chmin(int ql , int qr , int qv , int ind=1 , int l=0 , int r=N-1){
	push(ind,l,r);
	if(l >= ql and r <= qr){
		lazy[ind] = qv;
		push(ind,l,r);
		return;
	}
	else if(l > qr or r < ql)return;
	int mid = (l + r) / 2;
	chmin(ql,qr,qv,ind*2,l,mid);
	chmin(ql,qr,qv,ind*2+1,mid+1,r);
	tree[ind] = max(tree[ind*2] , tree[ind*2+1]);
}
int querymax(int ql , int qr , int ind=1 , int l=0 , int r=N-1){
	push(ind,l,r);
	if(l >= ql and r <= qr)return tree[ind];
	else if(l > qr or r < ql)return -inf;
	int mid = (l + r) / 2;
	return max(querymax(ql,qr,ind*2,l,mid) , querymax(ql,qr,ind*2+1,mid+1,r));
}
void solve(){
    int n,m,q;
    cin >> n >> m >> q;
    pair<int,int>ran[m];
    for(int i = 0;i<m;i++){
    	cin >> ran[i].first >> ran[i].second;
    	ran[i].first--;
    	ran[i].second--;
    }
    array<int,3>query[q];
    for(int i = 0;i<q;i++){
    	cin >> query[i][0] >> query[i][1];
    	query[i][0]--;
    	query[i][1]--;
    	query[i][2] = i;
    }
    sort(ran , ran + m);
    sort(query , query + q);
    int ptr0 = m-1 , ptr1 = q-1 , ans[q];
    for(int i = n-1;i>=0;i--){
    	while(ptr0>=0 and ran[ptr0].first >= i){
    		chmin(ran[ptr0].first , ran[ptr0].second , ran[ptr0].second);
    		ptr0--;
    	}
    	while(ptr1>=0 and query[ptr1][0] >= i){
    		ans[query[ptr1][2]] = querymax(query[ptr1][0] , query[ptr1][1]) <= query[ptr1][1];
    		ptr1--;
    	}
    }
    for(int i = 0;i<q;i++)
    	cout << (ans[i] ? "YES" : "NO") << '\n';
   	cout << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase=1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << 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