oj.uz

Submission #889967

# Submission time Handle Problem Language Result Execution time Memory
889967 2023-12-20T10:26:05 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 1379 ms 168804 KB 
//order_of_key(k): Number of items strictly smaller than k .
//find_by_order(k): K-th element in a set (counting from zero).

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define file(s) if(fopen(s".in","r")) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define all(x) (x).begin(), (x).end()
#define len(x) (int)x.size()
#define tm (tl + tr >> 1)
#define ls v << 1, tl, tm
#define rs v << 1 | 1, tm + 1, tr
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define elif else if
#define F first
#define S second
#define int long long

using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef long double ld;

const int MOD = 1e9 + 7;
const int N = 2e6 + 7;
const int P = 911;
const ll INF = 1e18;

int rnd() {
	int x = rand() << 15;
	return x ^ rand();
}

int n, a[N], t[N << 2];

void upd(int pos, int val, int v = 1, int tl = 1, int tr = n) {
	if (tl >= tr) {
		t[v] = max(t[v], val);
		return;
	}
	if (pos <= tm) upd(pos, val, ls);
	else upd(pos, val, rs);
	t[v] = max(t[v << 1], t[v << 1 | 1]);
}

int get(int l, int r, int v = 1, int tl = 1, int tr = n) {
	if (l <= tl && tr <= r) return t[v];
	if (r < tl || tr < l) return 0;
	return max(get(l, r, ls), get(l, r, rs));
}

int ql[N], qr[N], ans[N], k[N];
vector <int> act[N];

void GazizMadi() {
	int m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> ql[i] >> qr[i] >> k[i];
		act[ql[i]].pb(i); 
	}
	vector <int> st;
	for (int i = n; i; i--) {
		while (len(st)) {
			int j = st.back();
			if (a[i] <= a[j]) break;
			upd(j, a[i] + a[j]);
			st.popb();
		}
		st.pb(i);
		for (int it: act[i]) {
			int l = i, r = qr[it];
			ans[it] = (get(l, r) <= k[it] ? 1 : 0);
			// cout << l << ' ' << r << ' ' << get(l, r) << '\n';
		}
	}
	for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
}

const bool Cases = 0;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	srand(time(0));
	int TT = 1;
	if (Cases) cin >> TT;
	for (int i = 1; i <= TT; i++) {
		//cout << "Case " << i << ": ";
		GazizMadi();
	}
}

Compilation message

sortbooks.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:13:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
sortbooks.cpp:51:13: note: in expansion of macro 'tm'
   51 |  if (pos <= tm) upd(pos, val, ls);
      |             ^~
sortbooks.cpp:13:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
sortbooks.cpp:14:24: note: in expansion of macro 'tm'
   14 | #define ls v << 1, tl, tm
      |                        ^~
sortbooks.cpp:51:31: note: in expansion of macro 'ls'
   51 |  if (pos <= tm) upd(pos, val, ls);
      |                               ^~
sortbooks.cpp:13:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
sortbooks.cpp:15:24: note: in expansion of macro 'tm'
   15 | #define rs v << 1 | 1, tm + 1, tr
      |                        ^~
sortbooks.cpp:52:21: note: in expansion of macro 'rs'
   52 |  else upd(pos, val, rs);
      |                     ^~
sortbooks.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:13:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
sortbooks.cpp:14:24: note: in expansion of macro 'tm'
   14 | #define ls v << 1, tl, tm
      |                        ^~
sortbooks.cpp:59:23: note: in expansion of macro 'ls'
   59 |  return max(get(l, r, ls), get(l, r, rs));
      |                       ^~
sortbooks.cpp:13:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 | #define tm (tl + tr >> 1)
      |             ~~~^~~~
sortbooks.cpp:15:24: note: in expansion of macro 'tm'
   15 | #define rs v << 1 | 1, tm + 1, tr
      |                        ^~
sortbooks.cpp:59:38: note: in expansion of macro 'rs'
   59 |  return max(get(l, r, ls), get(l, r, rs));
      |                                      ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 55896 KB Output is correct
2 Correct 11 ms 55900 KB Output is correct
3 Correct 11 ms 56060 KB Output is correct
4 Correct 11 ms 55900 KB Output is correct
5 Correct 11 ms 55900 KB Output is correct
6 Correct 11 ms 56072 KB Output is correct
7 Correct 11 ms 55900 KB Output is correct
8 Correct 12 ms 55900 KB Output is correct
9 Correct 11 ms 55900 KB Output is correct
10 Correct 12 ms 55896 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 55896 KB Output is correct
2 Correct 11 ms 55900 KB Output is correct
3 Correct 11 ms 56060 KB Output is correct
4 Correct 11 ms 55900 KB Output is correct
5 Correct 11 ms 55900 KB Output is correct
6 Correct 11 ms 56072 KB Output is correct
7 Correct 11 ms 55900 KB Output is correct
8 Correct 12 ms 55900 KB Output is correct
9 Correct 11 ms 55900 KB Output is correct
10 Correct 12 ms 55896 KB Output is correct
11 Correct 13 ms 55900 KB Output is correct
12 Correct 14 ms 56060 KB Output is correct
13 Correct 13 ms 56156 KB Output is correct
14 Correct 15 ms 56408 KB Output is correct
15 Correct 15 ms 56296 KB Output is correct
16 Correct 14 ms 56252 KB Output is correct
17 Correct 13 ms 56156 KB Output is correct
18 Correct 14 ms 56156 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1233 ms 133916 KB Output is correct
2 Correct 1279 ms 133852 KB Output is correct
3 Correct 1262 ms 134060 KB Output is correct
4 Correct 1308 ms 133972 KB Output is correct
5 Correct 1028 ms 124752 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 66900 KB Output is correct
2 Correct 94 ms 65876 KB Output is correct
3 Correct 75 ms 65232 KB Output is correct
4 Correct 78 ms 65264 KB Output is correct
5 Correct 75 ms 65308 KB Output is correct
6 Correct 67 ms 66512 KB Output is correct
7 Correct 61 ms 66320 KB Output is correct
8 Correct 70 ms 65748 KB Output is correct
9 Correct 39 ms 61140 KB Output is correct
10 Correct 79 ms 65492 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 55896 KB Output is correct
2 Correct 11 ms 55900 KB Output is correct
3 Correct 11 ms 56060 KB Output is correct
4 Correct 11 ms 55900 KB Output is correct
5 Correct 11 ms 55900 KB Output is correct
6 Correct 11 ms 56072 KB Output is correct
7 Correct 11 ms 55900 KB Output is correct
8 Correct 12 ms 55900 KB Output is correct
9 Correct 11 ms 55900 KB Output is correct
10 Correct 12 ms 55896 KB Output is correct
11 Correct 13 ms 55900 KB Output is correct
12 Correct 14 ms 56060 KB Output is correct
13 Correct 13 ms 56156 KB Output is correct
14 Correct 15 ms 56408 KB Output is correct
15 Correct 15 ms 56296 KB Output is correct
16 Correct 14 ms 56252 KB Output is correct
17 Correct 13 ms 56156 KB Output is correct
18 Correct 14 ms 56156 KB Output is correct
19 Correct 185 ms 73512 KB Output is correct
20 Correct 189 ms 73636 KB Output is correct
21 Correct 191 ms 73296 KB Output is correct
22 Correct 170 ms 78672 KB Output is correct
23 Correct 162 ms 78568 KB Output is correct
24 Correct 145 ms 75188 KB Output is correct
25 Correct 139 ms 75192 KB Output is correct
26 Correct 153 ms 76236 KB Output is correct
27 Correct 154 ms 76236 KB Output is correct
28 Correct 159 ms 76716 KB Output is correct
29 Correct 167 ms 77260 KB Output is correct
30 Correct 170 ms 77252 KB Output is correct
31 Correct 164 ms 77256 KB Output is correct
32 Correct 171 ms 77164 KB Output is correct
33 Correct 170 ms 77168 KB Output is correct
34 Correct 131 ms 76680 KB Output is correct
35 Correct 127 ms 76860 KB Output is correct
36 Correct 139 ms 76464 KB Output is correct
37 Correct 131 ms 76568 KB Output is correct
38 Correct 126 ms 76848 KB Output is correct
39 Correct 148 ms 76100 KB Output is correct
40 Correct 122 ms 73604 KB Output is correct
41 Correct 142 ms 75464 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 55896 KB Output is correct
2 Correct 11 ms 55900 KB Output is correct
3 Correct 11 ms 56060 KB Output is correct
4 Correct 11 ms 55900 KB Output is correct
5 Correct 11 ms 55900 KB Output is correct
6 Correct 11 ms 56072 KB Output is correct
7 Correct 11 ms 55900 KB Output is correct
8 Correct 12 ms 55900 KB Output is correct
9 Correct 11 ms 55900 KB Output is correct
10 Correct 12 ms 55896 KB Output is correct
11 Correct 13 ms 55900 KB Output is correct
12 Correct 14 ms 56060 KB Output is correct
13 Correct 13 ms 56156 KB Output is correct
14 Correct 15 ms 56408 KB Output is correct
15 Correct 15 ms 56296 KB Output is correct
16 Correct 14 ms 56252 KB Output is correct
17 Correct 13 ms 56156 KB Output is correct
18 Correct 14 ms 56156 KB Output is correct
19 Correct 1233 ms 133916 KB Output is correct
20 Correct 1279 ms 133852 KB Output is correct
21 Correct 1262 ms 134060 KB Output is correct
22 Correct 1308 ms 133972 KB Output is correct
23 Correct 1028 ms 124752 KB Output is correct
24 Correct 94 ms 66900 KB Output is correct
25 Correct 94 ms 65876 KB Output is correct
26 Correct 75 ms 65232 KB Output is correct
27 Correct 78 ms 65264 KB Output is correct
28 Correct 75 ms 65308 KB Output is correct
29 Correct 67 ms 66512 KB Output is correct
30 Correct 61 ms 66320 KB Output is correct
31 Correct 70 ms 65748 KB Output is correct
32 Correct 39 ms 61140 KB Output is correct
33 Correct 79 ms 65492 KB Output is correct
34 Correct 185 ms 73512 KB Output is correct
35 Correct 189 ms 73636 KB Output is correct
36 Correct 191 ms 73296 KB Output is correct
37 Correct 170 ms 78672 KB Output is correct
38 Correct 162 ms 78568 KB Output is correct
39 Correct 145 ms 75188 KB Output is correct
40 Correct 139 ms 75192 KB Output is correct
41 Correct 153 ms 76236 KB Output is correct
42 Correct 154 ms 76236 KB Output is correct
43 Correct 159 ms 76716 KB Output is correct
44 Correct 167 ms 77260 KB Output is correct
45 Correct 170 ms 77252 KB Output is correct
46 Correct 164 ms 77256 KB Output is correct
47 Correct 171 ms 77164 KB Output is correct
48 Correct 170 ms 77168 KB Output is correct
49 Correct 131 ms 76680 KB Output is correct
50 Correct 127 ms 76860 KB Output is correct
51 Correct 139 ms 76464 KB Output is correct
52 Correct 131 ms 76568 KB Output is correct
53 Correct 126 ms 76848 KB Output is correct
54 Correct 148 ms 76100 KB Output is correct
55 Correct 122 ms 73604 KB Output is correct
56 Correct 142 ms 75464 KB Output is correct
57 Correct 1373 ms 168692 KB Output is correct
58 Correct 1379 ms 168804 KB Output is correct
59 Correct 1170 ms 165440 KB Output is correct
60 Correct 1222 ms 165188 KB Output is correct
61 Correct 1203 ms 165000 KB Output is correct
62 Correct 1175 ms 165176 KB Output is correct
63 Correct 729 ms 148016 KB Output is correct
64 Correct 746 ms 147628 KB Output is correct
65 Correct 1036 ms 155800 KB Output is correct
66 Correct 985 ms 155724 KB Output is correct
67 Correct 1008 ms 156088 KB Output is correct
68 Correct 1063 ms 160024 KB Output is correct
69 Correct 1068 ms 159596 KB Output is correct
70 Correct 1055 ms 159020 KB Output is correct
71 Correct 1064 ms 158988 KB Output is correct
72 Correct 1079 ms 158956 KB Output is correct
73 Correct 669 ms 151980 KB Output is correct
74 Correct 675 ms 152724 KB Output is correct
75 Correct 696 ms 151704 KB Output is correct
76 Correct 704 ms 152036 KB Output is correct
77 Correct 682 ms 152024 KB Output is correct
78 Correct 869 ms 152728 KB Output is correct
79 Correct 639 ms 135840 KB Output is correct
80 Correct 927 ms 153188 KB Output is correct