oj.uz

Submission #828192

# Submission time Handle Problem Language Result Execution time Memory
828192 2023-08-17T06:31:52 Z 반딧불(#10380) Curtains (NOI23_curtains) C++17
0 / 100
 12 ms 23804 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
	pair<int, int> tree[1<<20];

	pair<int, int> merge(pair<int, int> a, pair<int, int> b){
		if(!a.second) return b;
		if(!b.second) return a;
		if(a.second + 1 < b.first) return make_pair(0, 0);
		return make_pair(a.first, max(a.second, b.second));
	}

	void update(int i, int l, int r, int x, pair<int, int> p){
		if(l==r){
			tree[i] = p;
			return;
		}
		int m = (l+r)>>1;
		if(x<=m) update(i*2, l, m, x, p);
		else update(i*2+1, m+1, r, x, p);
		tree[i] = merge(tree[i*2], tree[i*2+1]);
	}

	pair<int, int> query(int i, int l, int r, int s, int e){
		if(r<s || e<l) return make_pair(0, 0);
		if(s<=l && r<=e) return tree[i];
		int m = (l+r)>>1;
		return merge(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
	}
} tree;

int n, k, q;
vector<pair<int, int> > vec;
vector<int> intvOn[500002];
vector<pair<int, int> > queries[500002];
int loc[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.push_back(make_pair(l, r));
	}
	for(int i=1; i<=q; i++){
		int l, r;
		scanf("%d %d", &l, &r);
		queries[r].push_back(make_pair(l, i));
	}

	vec.push_back(make_pair(0, 0));
	sort(vec.begin(), vec.end());
	for(int i=1; i<=k; i++){
		intvOn[vec[i].second].push_back(i);
	}

	for(int i=1; i<=n; i++){
		loc[i] = loc[i-1];
		while(loc[i] <= n && vec[loc[i]].first < i) loc[i]++;
	}
	//for(int i=1; i<=n; i++) printf("loc[%d]: %d\n", i, loc[i]);

	for(int i=1; i<=n; i++){
		for(int x: intvOn[i]){
			tree.update(1, 1, n, x, vec[x]);
		}
		for(pair<int, int> p: queries[i]){
			int l = p.first, idx = p.second;
			pair<int, int> pr = tree.query(1, 1, n, loc[l], n);
			if(pr == make_pair(l, i)) ans[idx] = 1;
		}
	}
	for(int i=1; i<=q; i++) printf("%s\n", ans[i] ? "YES" : "NO");
}

Compilation message

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

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 36.0

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

Subtask #6
0 / 20.0

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