oj.uz

Submission #886045

# Submission time Handle Problem Language Result Execution time Memory
886045 2023-12-11T12:17:58 Z vjudge1 Curtains (NOI23_curtains) C++17
0 / 100
 2 ms 8028 KB 
#include <bits/stdc++.h>
using namespace std;
#define tol(bi) (1LL<<((int)(bi)))
typedef long long ll;
constexpr int MOD = 1e9+7;
constexpr int MAXN = 2000005;
int segtree[MAXN];
struct SegTree{
	int sz;
	SegTree(int n){
		sz=tol(ceil(log2(n)+1)-1);
	}
	void dallan(int node){
		if (node*2+1<sz){
			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 = sz/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 = sz/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(){
	fill(segtree,segtree+MAXN,-1);
	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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Incorrect 2 ms 8028 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Incorrect 2 ms 8028 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Incorrect 2 ms 8028 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8024 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Incorrect 2 ms 8028 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Incorrect 2 ms 8028 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Incorrect 2 ms 8028 KB Output isn't correct
4 Halted 0 ms 0 KB -