oj.uz

답안 #828148

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
828148 2023-08-17T06:04:05 Z 반딧불(#10380) Curtains (NOI23_curtains) C++17
0 / 100
 13 ms 23916 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
	int treeMin[1<<20], treeMax[1<<20], lazy[1<<20];

	void init(int i, int l, int r){
		treeMin[i] = l, treeMax[i] = r;
		if(l==r) return;
		int m = (l+r)>>1;
		init(i*2, l, m);
		init(i*2+1, m+1, r);
	}

	void propagate(int i, int l, int r){
		if(!lazy[i]) return;
		treeMin[i] = max(treeMin[i], lazy[i]);
		treeMax[i] = max(treeMax[i], lazy[i]);
		if(l!=r){
			lazy[i*2] = max(lazy[i*2], lazy[i]);
			lazy[i*2+1] = max(lazy[i*2+1], lazy[i]);
		}
		lazy[i] = 0;
	}

	void update(int i, int l, int r, int s, int e, int x){
		propagate(i, l, r);
		if(r<s || e<l) return;
		if(s<=l && r<=e){
			lazy[i] = x;
			propagate(i, l, r);
			return;
		}
		int m = (l+r)>>1;
		update(i*2, l, m, s, e, x);
		update(i*2+1, m+1, r, s, e, x);
		treeMax[i] = max(treeMax[i*2], treeMax[i*2+1]);
		treeMin[i] = min(treeMin[i*2], treeMin[i*2+1]);
	}

	int query(int i, int l, int r, int x){
		propagate(i, l, r);
		if(l==r) return treeMax[i];
		int m = (l+r)>>1;
		if(x<=m) return query(i*2, l, m, x);
		else return query(i*2+1, m+1, r, x);
	}

	int atLeast(int i, int l, int r, int x){
		if(l==r) return l;
		int m = (l+r)>>1;
		if(treeMax[i*2] >= x) return atLeast(i*2, l, m, x);
		else return atLeast(i*2+1, m+1, r, x);
	}
} tree;

int n, k, q;
vector<int> vec[500002];
vector<pair<int, int> > queries[500002];
int ans[500002];

int main(){
	scanf("%d %d %d", &n, &k, &q);
	for(int i=1; i<=k; i++){
		int l, r;
		scanf("%d %d", &l, &r);
		vec[r].push_back(l);
	}
	for(int i=1; i<=q; i++){
		int l, r;
		scanf("%d %d", &l, &r);
		queries[r].push_back(make_pair(l, i));
	}
	tree.init(1, 1, n);
	for(int i=1; i<=n; i++){
		for(int x: vec[i]){
			int y = tree.atLeast(1, 1, n, x-1);
			tree.update(1, 1, n, y, i, i);
			//printf("Updated %d to %d\n", y, i);
		}
		for(pair<int, int> p: queries[i]){
			int v = tree.query(1, 1, n, p.first);
			ans[p.second] = v == i;
		}
	}
	for(int i=1; i<=q; i++) printf("%s\n", ans[i] ? "YES" : "NO");
}

Compilation message

curtains.cpp: In function 'int main()':
curtains.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |  scanf("%d %d %d", &n, &k, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   scanf("%d %d", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~
curtains.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   scanf("%d %d", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Incorrect 13 ms 23916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Incorrect 13 ms 23916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Incorrect 13 ms 23916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23812 KB Output is correct
2 Incorrect 11 ms 23776 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Incorrect 13 ms 23916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Incorrect 13 ms 23916 KB Output isn't correct
3 Halted 0 ms 0 KB -