oj.uz

Submission #891719

# Submission time Handle Problem Language Result Execution time Memory
891719 2023-12-23T18:37:37 Z pubin06 Curtains (NOI23_curtains) C++14
100 / 100
 635 ms 123644 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define sz(v) (int)(v).size()
using namespace std;

const int MXn = 500005;

int n, m, q;
int BIT1[MXn], BIT2[MXn];
void update1(int R, int i, int val) {
	for (; i <= R; i += (i & (-i))) BIT1[i] = min(BIT1[i], val);
}
int get1(int i) {
	int res1 = n + 1;
	for (; i; i -= (i & (-i))) res1 = min(res1, BIT1[i]);
	return res1;
}
void update2(int i, int val) {
	for (; i; i -= (i & (-i))) BIT2[i] = max(BIT2[i], val);
}
int get2(int R, int i) {
	int res2 = 0;
	for (; i <= R; i += (i & (-i))) res2 = max(res2, BIT2[i]);
	return res2;
}

bool onRange(int x, int L, int R) {
	return L <= x && x <= R;
}
int Lf[MXn], Rt[MXn];
bool ans[MXn];
vector<int> r[MXn], l[MXn];
void DnC(int lo, int hi, vector<pair<int, int>> segs, vector<pair<pair<int, int>, int>> qries) {
	if (lo == hi) {
		if (sz(segs)) {
			for (auto qry: qries) {
				ans[qry.se] = true;
			}
		}
		return;
	}
	int mid = (lo + hi) >> 1;
	vector<pair<int, int>> segsL, segsR;
	vector<pair<pair<int, int>, int>> qL, qR;
	for (int i = lo; i <= hi; i++) {
		r[i].clear(), l[i].clear();
	}
	for (auto seg: segs) {
		if (seg.se <= mid) segsL.push_back(seg);
		else r[seg.se].push_back(seg.fi);
		if (seg.fi > mid) segsR.push_back(seg);
		else l[seg.fi].push_back(seg.se);
	}
	for (int i = 1; i <= mid - lo + 1; i++) BIT1[i] = n + 1;
	for (int i = 1; i <= hi - mid; i++) BIT2[i] = 0;
	for (int i = mid; i >= lo; i--) {
		Lf[i] = n + 1;
		for (int j: l[i]) {
			if (j < mid) {
				Lf[i] = min(Lf[i], get1(j + 1 - lo + 1));
			} else {
				Lf[i] = min(Lf[i], j);
			}
		}
		update1(mid - lo + 1, i - lo + 1, Lf[i]);
	}
	for (int j = mid + 1; j <= hi; j++) {
		Rt[j] = 0;
		for (int i: r[j]) {
			if (i > mid + 1) {
				Rt[j] = max(Rt[j], get2(hi - mid, i - 1 - mid));
			} else {
				Rt[j] = max(Rt[j], i);
			}
		}
		update2(j - mid, Rt[j]);
	}
	for (auto qry: qries) {
		int L = qry.fi.fi, R = qry.fi.se;
		if (R <= mid) {
			qL.push_back(qry);
		} else if (L > mid) {
			qR.push_back(qry);
		} else {
			if (onRange(Lf[L], mid, R) && onRange(Rt[R], L, mid + 1)) ans[qry.se] = true;
		}
	}
	
	if (lo <= mid && sz(segsL) && sz(qL)) DnC(lo, mid, segsL, qL);
	if (mid + 1 <= hi && sz(segsR) && sz(qR)) DnC(mid + 1, hi, segsR, qR);
}
vector<pair<int, int>> segs;
vector<pair<pair<int, int>, int>> qries;

signed main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    #define TASK "CURTAINS"
    if (ifstream(TASK".INP")) {
    	freopen(TASK".INP", "r", stdin);
    	freopen(TASK".OUT", "w", stdout);
    }
    
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1, li, ri; i <= m; i++) {
    	scanf("%d%d", &li, &ri);
    	segs.push_back({li, ri});
    }
    for (int i = 1, u, v; i <= q; i++) {
    	scanf("%d%d", &u, &v);
    	qries.push_back({{u, v}, i});
    }
    DnC(1, n, segs, qries);
    for (int i = 1; i <= q; i++) printf(ans[i] ? "YES\n" : "NO\n");
    
    return 0;
}
// Revive! >:)

Compilation message

curtains.cpp: In function 'int main()':
curtains.cpp:102:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |      freopen(TASK".INP", "r", stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:103:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |      freopen(TASK".OUT", "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |     scanf("%d%d%d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:108:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |      scanf("%d%d", &li, &ri);
      |      ~~~~~^~~~~~~~~~~~~~~~~~
curtains.cpp:112:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |      scanf("%d%d", &u, &v);
      |      ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.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 Correct 8 ms 31324 KB Output is correct
4 Correct 6 ms 31356 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31324 KB Output is correct
7 Correct 7 ms 31420 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 8 ms 31324 KB Output is correct
10 Correct 6 ms 31324 KB Output is correct
11 Correct 7 ms 31452 KB Output is correct
12 Correct 7 ms 31452 KB Output is correct

Subtask #2
6.0 / 6.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 Correct 8 ms 31324 KB Output is correct
4 Correct 6 ms 31356 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31324 KB Output is correct
7 Correct 7 ms 31420 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 8 ms 31324 KB Output is correct
10 Correct 6 ms 31324 KB Output is correct
11 Correct 7 ms 31452 KB Output is correct
12 Correct 7 ms 31452 KB Output is correct
13 Correct 7 ms 31580 KB Output is correct
14 Correct 7 ms 31580 KB Output is correct
15 Correct 7 ms 31576 KB Output is correct
16 Correct 8 ms 31580 KB Output is correct
17 Correct 7 ms 31604 KB Output is correct
18 Correct 8 ms 31688 KB Output is correct
19 Correct 8 ms 31688 KB Output is correct
20 Correct 8 ms 31580 KB Output is correct
21 Correct 8 ms 31576 KB Output is correct

Subtask #3
15.0 / 15.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 Correct 8 ms 31324 KB Output is correct
4 Correct 6 ms 31356 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31324 KB Output is correct
7 Correct 7 ms 31420 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 8 ms 31324 KB Output is correct
10 Correct 6 ms 31324 KB Output is correct
11 Correct 7 ms 31452 KB Output is correct
12 Correct 7 ms 31452 KB Output is correct
13 Correct 7 ms 31580 KB Output is correct
14 Correct 7 ms 31580 KB Output is correct
15 Correct 7 ms 31576 KB Output is correct
16 Correct 8 ms 31580 KB Output is correct
17 Correct 7 ms 31604 KB Output is correct
18 Correct 8 ms 31688 KB Output is correct
19 Correct 8 ms 31688 KB Output is correct
20 Correct 8 ms 31580 KB Output is correct
21 Correct 8 ms 31576 KB Output is correct
22 Correct 91 ms 53712 KB Output is correct
23 Correct 92 ms 54060 KB Output is correct
24 Correct 106 ms 57792 KB Output is correct
25 Correct 168 ms 74824 KB Output is correct
26 Correct 91 ms 53968 KB Output is correct
27 Correct 172 ms 75116 KB Output is correct
28 Correct 175 ms 74972 KB Output is correct
29 Correct 94 ms 68332 KB Output is correct
30 Correct 90 ms 58276 KB Output is correct
31 Correct 94 ms 60288 KB Output is correct
32 Correct 167 ms 79028 KB Output is correct
33 Correct 88 ms 58612 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31324 KB Output is correct
2 Correct 7 ms 31404 KB Output is correct
3 Correct 7 ms 31580 KB Output is correct
4 Correct 7 ms 31400 KB Output is correct
5 Correct 7 ms 31580 KB Output is correct
6 Correct 8 ms 31580 KB Output is correct
7 Correct 7 ms 31616 KB Output is correct
8 Correct 87 ms 58268 KB Output is correct
9 Correct 93 ms 60076 KB Output is correct
10 Correct 169 ms 78772 KB Output is correct
11 Correct 86 ms 58616 KB Output is correct
12 Correct 54 ms 43208 KB Output is correct
13 Correct 52 ms 43308 KB Output is correct
14 Correct 54 ms 44744 KB Output is correct
15 Correct 54 ms 44488 KB Output is correct
16 Correct 55 ms 44912 KB Output is correct
17 Correct 54 ms 44492 KB Output is correct
18 Correct 322 ms 92708 KB Output is correct
19 Correct 348 ms 92652 KB Output is correct
20 Correct 324 ms 99780 KB Output is correct
21 Correct 315 ms 99440 KB Output is correct
22 Correct 304 ms 98744 KB Output is correct

Subtask #5
36.0 / 36.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 Correct 8 ms 31324 KB Output is correct
4 Correct 6 ms 31356 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31324 KB Output is correct
7 Correct 7 ms 31420 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 8 ms 31324 KB Output is correct
10 Correct 6 ms 31324 KB Output is correct
11 Correct 7 ms 31452 KB Output is correct
12 Correct 7 ms 31452 KB Output is correct
13 Correct 7 ms 31580 KB Output is correct
14 Correct 7 ms 31580 KB Output is correct
15 Correct 7 ms 31576 KB Output is correct
16 Correct 8 ms 31580 KB Output is correct
17 Correct 7 ms 31604 KB Output is correct
18 Correct 8 ms 31688 KB Output is correct
19 Correct 8 ms 31688 KB Output is correct
20 Correct 8 ms 31580 KB Output is correct
21 Correct 8 ms 31576 KB Output is correct
22 Correct 53 ms 40652 KB Output is correct
23 Correct 46 ms 40696 KB Output is correct
24 Correct 65 ms 43304 KB Output is correct
25 Correct 68 ms 43212 KB Output is correct
26 Correct 82 ms 49044 KB Output is correct
27 Correct 94 ms 49576 KB Output is correct
28 Correct 79 ms 43852 KB Output is correct
29 Correct 78 ms 47972 KB Output is correct
30 Correct 65 ms 43212 KB Output is correct
31 Correct 67 ms 43420 KB Output is correct
32 Correct 110 ms 45936 KB Output is correct
33 Correct 116 ms 47332 KB Output is correct
34 Correct 58 ms 46540 KB Output is correct
35 Correct 60 ms 45768 KB Output is correct
36 Correct 64 ms 46280 KB Output is correct
37 Correct 53 ms 43284 KB Output is correct
38 Correct 55 ms 43208 KB Output is correct
39 Correct 59 ms 45116 KB Output is correct
40 Correct 57 ms 44488 KB Output is correct
41 Correct 55 ms 44744 KB Output is correct
42 Correct 54 ms 44488 KB Output is correct

Subtask #6
20.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 Correct 8 ms 31324 KB Output is correct
4 Correct 6 ms 31356 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31324 KB Output is correct
7 Correct 7 ms 31420 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 8 ms 31324 KB Output is correct
10 Correct 6 ms 31324 KB Output is correct
11 Correct 7 ms 31452 KB Output is correct
12 Correct 7 ms 31452 KB Output is correct
13 Correct 7 ms 31580 KB Output is correct
14 Correct 7 ms 31580 KB Output is correct
15 Correct 7 ms 31576 KB Output is correct
16 Correct 8 ms 31580 KB Output is correct
17 Correct 7 ms 31604 KB Output is correct
18 Correct 8 ms 31688 KB Output is correct
19 Correct 8 ms 31688 KB Output is correct
20 Correct 8 ms 31580 KB Output is correct
21 Correct 8 ms 31576 KB Output is correct
22 Correct 91 ms 53712 KB Output is correct
23 Correct 92 ms 54060 KB Output is correct
24 Correct 106 ms 57792 KB Output is correct
25 Correct 168 ms 74824 KB Output is correct
26 Correct 91 ms 53968 KB Output is correct
27 Correct 172 ms 75116 KB Output is correct
28 Correct 175 ms 74972 KB Output is correct
29 Correct 94 ms 68332 KB Output is correct
30 Correct 90 ms 58276 KB Output is correct
31 Correct 94 ms 60288 KB Output is correct
32 Correct 167 ms 79028 KB Output is correct
33 Correct 88 ms 58612 KB Output is correct
34 Correct 6 ms 31324 KB Output is correct
35 Correct 7 ms 31404 KB Output is correct
36 Correct 7 ms 31580 KB Output is correct
37 Correct 7 ms 31400 KB Output is correct
38 Correct 7 ms 31580 KB Output is correct
39 Correct 8 ms 31580 KB Output is correct
40 Correct 7 ms 31616 KB Output is correct
41 Correct 87 ms 58268 KB Output is correct
42 Correct 93 ms 60076 KB Output is correct
43 Correct 169 ms 78772 KB Output is correct
44 Correct 86 ms 58616 KB Output is correct
45 Correct 54 ms 43208 KB Output is correct
46 Correct 52 ms 43308 KB Output is correct
47 Correct 54 ms 44744 KB Output is correct
48 Correct 54 ms 44488 KB Output is correct
49 Correct 55 ms 44912 KB Output is correct
50 Correct 54 ms 44492 KB Output is correct
51 Correct 322 ms 92708 KB Output is correct
52 Correct 348 ms 92652 KB Output is correct
53 Correct 324 ms 99780 KB Output is correct
54 Correct 315 ms 99440 KB Output is correct
55 Correct 304 ms 98744 KB Output is correct
56 Correct 53 ms 40652 KB Output is correct
57 Correct 46 ms 40696 KB Output is correct
58 Correct 65 ms 43304 KB Output is correct
59 Correct 68 ms 43212 KB Output is correct
60 Correct 82 ms 49044 KB Output is correct
61 Correct 94 ms 49576 KB Output is correct
62 Correct 79 ms 43852 KB Output is correct
63 Correct 78 ms 47972 KB Output is correct
64 Correct 65 ms 43212 KB Output is correct
65 Correct 67 ms 43420 KB Output is correct
66 Correct 110 ms 45936 KB Output is correct
67 Correct 116 ms 47332 KB Output is correct
68 Correct 58 ms 46540 KB Output is correct
69 Correct 60 ms 45768 KB Output is correct
70 Correct 64 ms 46280 KB Output is correct
71 Correct 53 ms 43284 KB Output is correct
72 Correct 55 ms 43208 KB Output is correct
73 Correct 59 ms 45116 KB Output is correct
74 Correct 57 ms 44488 KB Output is correct
75 Correct 55 ms 44744 KB Output is correct
76 Correct 54 ms 44488 KB Output is correct
77 Correct 407 ms 91972 KB Output is correct
78 Correct 398 ms 92088 KB Output is correct
79 Correct 559 ms 122292 KB Output is correct
80 Correct 635 ms 122336 KB Output is correct
81 Correct 606 ms 117328 KB Output is correct
82 Correct 540 ms 121196 KB Output is correct
83 Correct 397 ms 92092 KB Output is correct
84 Correct 406 ms 92412 KB Output is correct
85 Correct 627 ms 103180 KB Output is correct
86 Correct 327 ms 123644 KB Output is correct
87 Correct 341 ms 117412 KB Output is correct
88 Correct 517 ms 107188 KB Output is correct