oj.uz

Submission #965751

# Submission time Handle Problem Language Result Execution time Memory
965751 2024-04-19T06:53:06 Z Trisanu_Das Curtains (NOI23_curtains) C++17
100 / 100
 593 ms 75280 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 7;
const int inf = 1e9 + 7;
struct SEGT{
	int tree[N];
	SEGT(){
		for(int i = 0;i<N;i++) tree[i] = inf;
	}
	void update(int ind , int l , int r , int ql , int qr){
		if(l >= ql and r <= qr){
			tree[ind] = min(tree[ind] , qr);
			return;
		}
		else if(l > qr or r < ql) return;
		else{
			int mid = (l+r)/2;
			update(ind*2,l,mid,ql,qr);
			update(ind*2+1,mid+1,r,ql,qr);
			tree[ind] = min(tree[ind] , max(tree[ind*2] , tree[ind*2+1]));
		}
	}
	bool query(int ind , int l , int r , int ql , int qr){
		if(l >= ql and r <= qr) return tree[ind] <= qr;
		else if(l > qr or r < ql) return 1;
		else{
			int mid = (l+r)/2;
			return query(ind*2,l,mid,ql,qr) and query(ind*2+1,mid+1,r,ql,qr);
		}
	}
} segt;
void solve(){
	int n,m,q;
	cin >> n >> m >> q;
	vector < int > ran[n+1];
	vector < pair < int , int > > query[n+1];
	for(int i = 0;i<m;i++){
		int x,y;
		cin >> x >> y;
		ran[x].push_back(y);
	}
	for(int i = 0;i<q;i++){
		int x,y;
		cin >> x >> y;
		query[x].push_back({y,i});
	}
	int ans[q];
	for(int i = n;i>0;i--){
		for(auto itr : ran[i]) segt.update(1,1,n,i,itr);
		for(auto itr : query[i]) ans[itr.second] = segt.query(1,1,n,i,itr.first);
	}
	for(int i = 0;i<q;i++) cout << (ans[i] ? "YES\n" : "NO\n");
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	solve();
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8036 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 2 ms 8292 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8096 KB Output is correct
7 Correct 3 ms 8280 KB Output is correct
8 Correct 2 ms 8280 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Correct 2 ms 8280 KB Output is correct
11 Correct 2 ms 8284 KB Output is correct
12 Correct 2 ms 8284 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8036 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 2 ms 8292 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8096 KB Output is correct
7 Correct 3 ms 8280 KB Output is correct
8 Correct 2 ms 8280 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Correct 2 ms 8280 KB Output is correct
11 Correct 2 ms 8284 KB Output is correct
12 Correct 2 ms 8284 KB Output is correct
13 Correct 4 ms 8284 KB Output is correct
14 Correct 3 ms 8284 KB Output is correct
15 Correct 3 ms 8280 KB Output is correct
16 Correct 4 ms 8280 KB Output is correct
17 Correct 3 ms 8280 KB Output is correct
18 Correct 3 ms 8284 KB Output is correct
19 Correct 3 ms 8284 KB Output is correct
20 Correct 3 ms 8284 KB Output is correct
21 Correct 3 ms 8284 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8036 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 2 ms 8292 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8096 KB Output is correct
7 Correct 3 ms 8280 KB Output is correct
8 Correct 2 ms 8280 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Correct 2 ms 8280 KB Output is correct
11 Correct 2 ms 8284 KB Output is correct
12 Correct 2 ms 8284 KB Output is correct
13 Correct 4 ms 8284 KB Output is correct
14 Correct 3 ms 8284 KB Output is correct
15 Correct 3 ms 8280 KB Output is correct
16 Correct 4 ms 8280 KB Output is correct
17 Correct 3 ms 8280 KB Output is correct
18 Correct 3 ms 8284 KB Output is correct
19 Correct 3 ms 8284 KB Output is correct
20 Correct 3 ms 8284 KB Output is correct
21 Correct 3 ms 8284 KB Output is correct
22 Correct 98 ms 21544 KB Output is correct
23 Correct 140 ms 22100 KB Output is correct
24 Correct 170 ms 23376 KB Output is correct
25 Correct 244 ms 28204 KB Output is correct
26 Correct 126 ms 21896 KB Output is correct
27 Correct 238 ms 28128 KB Output is correct
28 Correct 248 ms 28184 KB Output is correct
29 Correct 97 ms 21844 KB Output is correct
30 Correct 100 ms 19120 KB Output is correct
31 Correct 110 ms 19740 KB Output is correct
32 Correct 214 ms 25528 KB Output is correct
33 Correct 101 ms 19128 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8024 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 2 ms 8284 KB Output is correct
5 Correct 3 ms 8484 KB Output is correct
6 Correct 3 ms 8284 KB Output is correct
7 Correct 3 ms 8284 KB Output is correct
8 Correct 101 ms 19256 KB Output is correct
9 Correct 110 ms 19608 KB Output is correct
10 Correct 218 ms 25528 KB Output is correct
11 Correct 101 ms 19084 KB Output is correct
12 Correct 70 ms 18120 KB Output is correct
13 Correct 67 ms 18120 KB Output is correct
14 Correct 48 ms 18144 KB Output is correct
15 Correct 52 ms 18120 KB Output is correct
16 Correct 56 ms 18236 KB Output is correct
17 Correct 49 ms 18196 KB Output is correct
18 Correct 408 ms 56768 KB Output is correct
19 Correct 439 ms 57020 KB Output is correct
20 Correct 308 ms 57540 KB Output is correct
21 Correct 304 ms 57528 KB Output is correct
22 Correct 306 ms 57276 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8036 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 2 ms 8292 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8096 KB Output is correct
7 Correct 3 ms 8280 KB Output is correct
8 Correct 2 ms 8280 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Correct 2 ms 8280 KB Output is correct
11 Correct 2 ms 8284 KB Output is correct
12 Correct 2 ms 8284 KB Output is correct
13 Correct 4 ms 8284 KB Output is correct
14 Correct 3 ms 8284 KB Output is correct
15 Correct 3 ms 8280 KB Output is correct
16 Correct 4 ms 8280 KB Output is correct
17 Correct 3 ms 8280 KB Output is correct
18 Correct 3 ms 8284 KB Output is correct
19 Correct 3 ms 8284 KB Output is correct
20 Correct 3 ms 8284 KB Output is correct
21 Correct 3 ms 8284 KB Output is correct
22 Correct 64 ms 13400 KB Output is correct
23 Correct 64 ms 13400 KB Output is correct
24 Correct 83 ms 19536 KB Output is correct
25 Correct 88 ms 19620 KB Output is correct
26 Correct 81 ms 21084 KB Output is correct
27 Correct 85 ms 21072 KB Output is correct
28 Correct 56 ms 18952 KB Output is correct
29 Correct 61 ms 20740 KB Output is correct
30 Correct 81 ms 19692 KB Output is correct
31 Correct 82 ms 19696 KB Output is correct
32 Correct 86 ms 20048 KB Output is correct
33 Correct 80 ms 20220 KB Output is correct
34 Correct 76 ms 19280 KB Output is correct
35 Correct 78 ms 19284 KB Output is correct
36 Correct 73 ms 19608 KB Output is correct
37 Correct 80 ms 18116 KB Output is correct
38 Correct 67 ms 18116 KB Output is correct
39 Correct 48 ms 18380 KB Output is correct
40 Correct 48 ms 18376 KB Output is correct
41 Correct 47 ms 18384 KB Output is correct
42 Correct 64 ms 18500 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8036 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8284 KB Output is correct
4 Correct 2 ms 8292 KB Output is correct
5 Correct 2 ms 8284 KB Output is correct
6 Correct 2 ms 8096 KB Output is correct
7 Correct 3 ms 8280 KB Output is correct
8 Correct 2 ms 8280 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Correct 2 ms 8280 KB Output is correct
11 Correct 2 ms 8284 KB Output is correct
12 Correct 2 ms 8284 KB Output is correct
13 Correct 4 ms 8284 KB Output is correct
14 Correct 3 ms 8284 KB Output is correct
15 Correct 3 ms 8280 KB Output is correct
16 Correct 4 ms 8280 KB Output is correct
17 Correct 3 ms 8280 KB Output is correct
18 Correct 3 ms 8284 KB Output is correct
19 Correct 3 ms 8284 KB Output is correct
20 Correct 3 ms 8284 KB Output is correct
21 Correct 3 ms 8284 KB Output is correct
22 Correct 98 ms 21544 KB Output is correct
23 Correct 140 ms 22100 KB Output is correct
24 Correct 170 ms 23376 KB Output is correct
25 Correct 244 ms 28204 KB Output is correct
26 Correct 126 ms 21896 KB Output is correct
27 Correct 238 ms 28128 KB Output is correct
28 Correct 248 ms 28184 KB Output is correct
29 Correct 97 ms 21844 KB Output is correct
30 Correct 100 ms 19120 KB Output is correct
31 Correct 110 ms 19740 KB Output is correct
32 Correct 214 ms 25528 KB Output is correct
33 Correct 101 ms 19128 KB Output is correct
34 Correct 2 ms 8024 KB Output is correct
35 Correct 2 ms 8284 KB Output is correct
36 Correct 2 ms 8284 KB Output is correct
37 Correct 2 ms 8284 KB Output is correct
38 Correct 3 ms 8484 KB Output is correct
39 Correct 3 ms 8284 KB Output is correct
40 Correct 3 ms 8284 KB Output is correct
41 Correct 101 ms 19256 KB Output is correct
42 Correct 110 ms 19608 KB Output is correct
43 Correct 218 ms 25528 KB Output is correct
44 Correct 101 ms 19084 KB Output is correct
45 Correct 70 ms 18120 KB Output is correct
46 Correct 67 ms 18120 KB Output is correct
47 Correct 48 ms 18144 KB Output is correct
48 Correct 52 ms 18120 KB Output is correct
49 Correct 56 ms 18236 KB Output is correct
50 Correct 49 ms 18196 KB Output is correct
51 Correct 408 ms 56768 KB Output is correct
52 Correct 439 ms 57020 KB Output is correct
53 Correct 308 ms 57540 KB Output is correct
54 Correct 304 ms 57528 KB Output is correct
55 Correct 306 ms 57276 KB Output is correct
56 Correct 64 ms 13400 KB Output is correct
57 Correct 64 ms 13400 KB Output is correct
58 Correct 83 ms 19536 KB Output is correct
59 Correct 88 ms 19620 KB Output is correct
60 Correct 81 ms 21084 KB Output is correct
61 Correct 85 ms 21072 KB Output is correct
62 Correct 56 ms 18952 KB Output is correct
63 Correct 61 ms 20740 KB Output is correct
64 Correct 81 ms 19692 KB Output is correct
65 Correct 82 ms 19696 KB Output is correct
66 Correct 86 ms 20048 KB Output is correct
67 Correct 80 ms 20220 KB Output is correct
68 Correct 76 ms 19280 KB Output is correct
69 Correct 78 ms 19284 KB Output is correct
70 Correct 73 ms 19608 KB Output is correct
71 Correct 80 ms 18116 KB Output is correct
72 Correct 67 ms 18116 KB Output is correct
73 Correct 48 ms 18380 KB Output is correct
74 Correct 48 ms 18376 KB Output is correct
75 Correct 47 ms 18384 KB Output is correct
76 Correct 64 ms 18500 KB Output is correct
77 Correct 586 ms 67400 KB Output is correct
78 Correct 581 ms 67412 KB Output is correct
79 Correct 584 ms 75236 KB Output is correct
80 Correct 593 ms 75280 KB Output is correct
81 Correct 545 ms 72692 KB Output is correct
82 Correct 478 ms 74144 KB Output is correct
83 Correct 579 ms 67444 KB Output is correct
84 Correct 589 ms 67400 KB Output is correct
85 Correct 572 ms 68432 KB Output is correct
86 Correct 464 ms 63828 KB Output is correct
87 Correct 496 ms 63448 KB Output is correct
88 Correct 528 ms 71752 KB Output is correct