# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
889967 | 2023-12-20T10:26:05 Z | vjudge1 | Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) | C++17 | 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
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 |