oj.uz

Submission #955905

# Submission time Handle Problem Language Result Execution time Memory
955905 2024-03-31T16:54:03 Z AlphaMale06 Curtains (NOI23_curtains) C++14
0 / 100
 13 ms 31324 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define int long long

struct query{
	int l, r, ind;
	string ans;
};

const int N = 5e5+3;
pair<int, int> lr[N];
int st[4*N], lz[4*N];
query qs[N];

void push(int v){
	int lc = 2*v+1;
	int rc = 2*v+2;
	st[lc]=max(st[lc], lz[v]);
	st[rc]=max(st[rc], lz[v]);
	lz[lc]=max(lz[lc], lz[v]);
	lz[rc]=max(lz[rc], lz[v]);
}

void Update(int v, int l, int r, int L, int R, int val){
	if(l>r || l>R || r<L)return;
	if(l>=L && r<=R){
		st[v]=max(st[v], val);
		lz[v]=max(lz[v], val);
		return;
	}
	push(v);
	int mid = l+r>>1;
	Update(2*v+1, l, mid, L, R, val);
	Update(2*v+2, mid+1, r, L, R, val);
	st[v]=min(st[2*v+1], st[2*v+2]);
}

int Get(int v, int l, int r, int L, int R){
	if(l>r || l>R || r<L)return 1e9;
	if(l>=L && r<=R)return st[v];
	push(v);
	int mid = l+r>>1;
	return min(Get(2*v+1, l, mid, L, R), Get(2*v+2, mid+1, r, L, R));
}

bool cmp1(query A, query B){
	return A.r<B.r;
}
bool cmp2(query A, query B){
	return A.ind < B.ind;
}

void solve(){
	int n, m, q;
	cin >> n >> m >> q;
	for(int i=0; i< m; i++){
		cin >> lr[i].S >> lr[i].F;
	}		
	sort(lr, lr+m);
	for(int i=0; i< m; i++){
		swap(lr[i].F, lr[i].S);
	}
	for(int i=0; i< q; i++){
		cin >> qs[i].l >> qs[i].r;
		qs[i].ind=i;
	}
	sort(qs, qs+q, cmp1);
	int p=0;
	for(int i=0; i< q; i++){
		while(p<m && lr[p].S<=qs[i].r){
			Update(0, 1, n, lr[i].F, lr[i].S, lr[i].F);
			p++;
		}
		if(Get(0, 1, n, qs[i].l, qs[i].r)>=qs[i].l)qs[i].ans="YES";
		else qs[i].ans="NO";
	}
	sort(qs, qs+q, cmp2);
	for(int i=0; i< q; i++){
		cout << qs[i].ans << '\n';
	}
}


signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Compilation message

curtains.cpp: In function 'void Update(long long int, long long int, long long int, long long int, long long int, long long int)':
curtains.cpp:41:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |  int mid = l+r>>1;
      |            ~^~
curtains.cpp: In function 'long long int Get(long long int, long long int, long long int, long long int, long long int)':
curtains.cpp:51:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |  int mid = l+r>>1;
      |            ~^~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31320 KB Output is correct
2 Incorrect 7 ms 31324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31320 KB Output is correct
2 Incorrect 7 ms 31324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31320 KB Output is correct
2 Incorrect 7 ms 31324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31320 KB Output is correct
2 Incorrect 7 ms 31324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31320 KB Output is correct
2 Incorrect 7 ms 31324 KB Output isn't correct
3 Halted 0 ms 0 KB -