oj.uz

Submission #1094885

# Submission time Handle Problem Language Result Execution time Memory
1094885 2024-09-30T17:56:23 Z Kerim Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 1075 ms 108372 KB 
#include "bits/stdc++.h"
 
using namespace std;
const int N = 1e6+6;
int arr[N], d[N], ans[N];
vector<int> queries[N];
int l[N], r[N], k[N], s[N<<2];
void upd(int p, int v, int nd, int x, int y){
	if (x == y){
		s[nd] = max(s[nd], v);
		return;
	}
	int mid = (x+y) >> 1;
	if (p <= mid)
		upd(p, v, nd<<1, x, mid);
	else
		upd(p, v, nd<<1|1, mid+1, y);
	s[nd] = max(s[nd<<1], s[nd<<1|1]);
}
int tap(int l, int r, int nd, int x, int y){
	if (l > y or x > r)
		return 0;
	if (l <= x and y <= r)
		return s[nd];
	int mid = (x+y) >> 1;
	return max(tap(l, r, nd<<1, x, mid), tap(l, r, nd<<1|1, mid+1, y));
}
int main(){
	// freopen("file.in", "r", stdin);
	int n, q;
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++)
		scanf("%d", arr+i);
	stack<int> st;
	for (int i = 1; i <= n; i++){
		while (!st.empty() and arr[st.top()] <= arr[i])
			st.pop();
		if (st.empty())
			d[i] = -1;
		else
			d[i] = st.top();
		st.push(i);
	}
	for (int i = 1; i <= q; i++){
		scanf("%d%d%d", l+i, r+i, k+i);
		queries[r[i]].push_back(i);
	}
	for (int j = 1; j <= n; j++){
		int i = d[j];
		if (~i)
			upd(i, arr[i]+arr[j], 1, 1, n);
		for (auto ind: queries[j])
			ans[ind] = tap(l[ind], r[ind], 1, 1, n) <= k[ind];
	}
	for (int i = 1; i <= q; i++)
		printf("%d\n", ans[i]);
	return 0;
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23896 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 9 ms 23948 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 10 ms 23928 KB Output is correct
6 Correct 9 ms 23900 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 10 ms 23900 KB Output is correct
10 Correct 10 ms 23896 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23896 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 9 ms 23948 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 10 ms 23928 KB Output is correct
6 Correct 9 ms 23900 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 10 ms 23900 KB Output is correct
10 Correct 10 ms 23896 KB Output is correct
11 Correct 11 ms 24152 KB Output is correct
12 Correct 12 ms 24156 KB Output is correct
13 Correct 11 ms 24232 KB Output is correct
14 Correct 14 ms 24156 KB Output is correct
15 Correct 13 ms 24152 KB Output is correct
16 Correct 13 ms 24152 KB Output is correct
17 Correct 12 ms 24152 KB Output is correct
18 Correct 12 ms 24156 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1075 ms 106836 KB Output is correct
2 Correct 964 ms 108208 KB Output is correct
3 Correct 963 ms 108116 KB Output is correct
4 Correct 951 ms 108372 KB Output is correct
5 Correct 859 ms 100128 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 30940 KB Output is correct
2 Correct 72 ms 30100 KB Output is correct
3 Correct 73 ms 29776 KB Output is correct
4 Correct 73 ms 29796 KB Output is correct
5 Correct 80 ms 30036 KB Output is correct
6 Correct 55 ms 28764 KB Output is correct
7 Correct 58 ms 28924 KB Output is correct
8 Correct 64 ms 29644 KB Output is correct
9 Correct 41 ms 27340 KB Output is correct
10 Correct 60 ms 29644 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23896 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 9 ms 23948 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 10 ms 23928 KB Output is correct
6 Correct 9 ms 23900 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 10 ms 23900 KB Output is correct
10 Correct 10 ms 23896 KB Output is correct
11 Correct 11 ms 24152 KB Output is correct
12 Correct 12 ms 24156 KB Output is correct
13 Correct 11 ms 24232 KB Output is correct
14 Correct 14 ms 24156 KB Output is correct
15 Correct 13 ms 24152 KB Output is correct
16 Correct 13 ms 24152 KB Output is correct
17 Correct 12 ms 24152 KB Output is correct
18 Correct 12 ms 24156 KB Output is correct
19 Correct 167 ms 40784 KB Output is correct
20 Correct 170 ms 40784 KB Output is correct
21 Correct 144 ms 38992 KB Output is correct
22 Correct 148 ms 38992 KB Output is correct
23 Correct 149 ms 39032 KB Output is correct
24 Correct 130 ms 36636 KB Output is correct
25 Correct 122 ms 36688 KB Output is correct
26 Correct 135 ms 37460 KB Output is correct
27 Correct 140 ms 37456 KB Output is correct
28 Correct 136 ms 37716 KB Output is correct
29 Correct 163 ms 38740 KB Output is correct
30 Correct 149 ms 38712 KB Output is correct
31 Correct 143 ms 38652 KB Output is correct
32 Correct 144 ms 38740 KB Output is correct
33 Correct 149 ms 38692 KB Output is correct
34 Correct 119 ms 36436 KB Output is correct
35 Correct 137 ms 36432 KB Output is correct
36 Correct 125 ms 36180 KB Output is correct
37 Correct 126 ms 36180 KB Output is correct
38 Correct 116 ms 36432 KB Output is correct
39 Correct 132 ms 37644 KB Output is correct
40 Correct 104 ms 35528 KB Output is correct
41 Correct 132 ms 36808 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23896 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 9 ms 23948 KB Output is correct
4 Correct 11 ms 23900 KB Output is correct
5 Correct 10 ms 23928 KB Output is correct
6 Correct 9 ms 23900 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 10 ms 23900 KB Output is correct
10 Correct 10 ms 23896 KB Output is correct
11 Correct 11 ms 24152 KB Output is correct
12 Correct 12 ms 24156 KB Output is correct
13 Correct 11 ms 24232 KB Output is correct
14 Correct 14 ms 24156 KB Output is correct
15 Correct 13 ms 24152 KB Output is correct
16 Correct 13 ms 24152 KB Output is correct
17 Correct 12 ms 24152 KB Output is correct
18 Correct 12 ms 24156 KB Output is correct
19 Correct 1075 ms 106836 KB Output is correct
20 Correct 964 ms 108208 KB Output is correct
21 Correct 963 ms 108116 KB Output is correct
22 Correct 951 ms 108372 KB Output is correct
23 Correct 859 ms 100128 KB Output is correct
24 Correct 82 ms 30940 KB Output is correct
25 Correct 72 ms 30100 KB Output is correct
26 Correct 73 ms 29776 KB Output is correct
27 Correct 73 ms 29796 KB Output is correct
28 Correct 80 ms 30036 KB Output is correct
29 Correct 55 ms 28764 KB Output is correct
30 Correct 58 ms 28924 KB Output is correct
31 Correct 64 ms 29644 KB Output is correct
32 Correct 41 ms 27340 KB Output is correct
33 Correct 60 ms 29644 KB Output is correct
34 Correct 167 ms 40784 KB Output is correct
35 Correct 170 ms 40784 KB Output is correct
36 Correct 144 ms 38992 KB Output is correct
37 Correct 148 ms 38992 KB Output is correct
38 Correct 149 ms 39032 KB Output is correct
39 Correct 130 ms 36636 KB Output is correct
40 Correct 122 ms 36688 KB Output is correct
41 Correct 135 ms 37460 KB Output is correct
42 Correct 140 ms 37456 KB Output is correct
43 Correct 136 ms 37716 KB Output is correct
44 Correct 163 ms 38740 KB Output is correct
45 Correct 149 ms 38712 KB Output is correct
46 Correct 143 ms 38652 KB Output is correct
47 Correct 144 ms 38740 KB Output is correct
48 Correct 149 ms 38692 KB Output is correct
49 Correct 119 ms 36436 KB Output is correct
50 Correct 137 ms 36432 KB Output is correct
51 Correct 125 ms 36180 KB Output is correct
52 Correct 126 ms 36180 KB Output is correct
53 Correct 116 ms 36432 KB Output is correct
54 Correct 132 ms 37644 KB Output is correct
55 Correct 104 ms 35528 KB Output is correct
56 Correct 132 ms 36808 KB Output is correct
57 Correct 980 ms 107152 KB Output is correct
58 Correct 929 ms 107092 KB Output is correct
59 Correct 833 ms 102932 KB Output is correct
60 Correct 853 ms 102996 KB Output is correct
61 Correct 910 ms 103104 KB Output is correct
62 Correct 923 ms 103152 KB Output is correct
63 Correct 624 ms 87124 KB Output is correct
64 Correct 607 ms 87092 KB Output is correct
65 Correct 772 ms 94360 KB Output is correct
66 Correct 772 ms 94396 KB Output is correct
67 Correct 782 ms 94548 KB Output is correct
68 Correct 876 ms 98900 KB Output is correct
69 Correct 883 ms 98940 KB Output is correct
70 Correct 775 ms 98384 KB Output is correct
71 Correct 789 ms 98388 KB Output is correct
72 Correct 817 ms 98320 KB Output is correct
73 Correct 619 ms 85080 KB Output is correct
74 Correct 611 ms 86100 KB Output is correct
75 Correct 612 ms 85200 KB Output is correct
76 Correct 578 ms 84816 KB Output is correct
77 Correct 604 ms 85172 KB Output is correct
78 Correct 743 ms 93888 KB Output is correct
79 Correct 547 ms 80320 KB Output is correct
80 Correct 741 ms 88920 KB Output is correct