oj.uz

Submission #497903

# Submission time Handle Problem Language Result Execution time Memory
497903 2021-12-24T04:36:20 Z Ierus Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 2885 ms 91332 KB 
#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/
using namespace std;
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
#define F first
#define S second
#define sz(x) (int)x.size()
#define int long long
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
const int E = 1e6+777;
const long long inf = 1e18+777;
const int N = 1e5+777;
const int MOD = 1e9+7;
const bool I = 1;
int n, que, a[E], t[E<<2], ans[E];
void update(int pos, int val, int v, int tl, int tr){
	if(tl == tr){
		t[v] = max(val, t[v]);
		return;
	}
	int tm = (tl + tr) / 2;
	if(pos <= tm) update(pos, val, v<<1, tl, tm);
	else update(pos, val, v<<1|1, tm+1, tr);
	t[v] = max(t[v<<1], t[v<<1|1]);
}
int get(int l, int r, int v, int tl, int tr){
	if(l <= tl && tr <= r) return t[v];
	if(tl > r || tr < l) return 0;
	int tm = (tl + tr) / 2;
	return max(get(l, r, v<<1, tl, tm), get(l, r, v<<1|1, tm+1, tr));
}
struct D{
	int l, x, i;
};
vector<D> g[E];
signed main(){
	cin >> n >> que;
	for(int i = 1; i <= n; ++i){
		cin >> a[i];
	}
	for(int l, r, x, i = 1; i <= que; ++i){
		cin >> l >> r >> x;
		g[r].pb({l, x, i});
	}
	deque<pair<int,int>> st;
	for(int i = 1; i <= n; ++i){
		while(!st.empty() && st.back().F <= a[i]) st.pop_back();
		if(!st.empty()) update(st.back().S, st.back().F + a[i], 1, 0, n);
		for(auto to : g[i]){
			int cur = get(to.l, i, 1, 0, n);
			ans[to.i] = (cur <= to.x);
		}
		st.push_back({a[i], i});
	}
	for(int i = 1; i <= que; ++i){
		cout << ans[i] << '\n';
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23760 KB Output is correct
2 Correct 13 ms 23816 KB Output is correct
3 Correct 13 ms 23756 KB Output is correct
4 Correct 13 ms 23756 KB Output is correct
5 Correct 14 ms 23756 KB Output is correct
6 Correct 16 ms 23848 KB Output is correct
7 Correct 14 ms 23816 KB Output is correct
8 Correct 14 ms 23800 KB Output is correct
9 Correct 14 ms 23844 KB Output is correct
10 Correct 13 ms 23756 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23760 KB Output is correct
2 Correct 13 ms 23816 KB Output is correct
3 Correct 13 ms 23756 KB Output is correct
4 Correct 13 ms 23756 KB Output is correct
5 Correct 14 ms 23756 KB Output is correct
6 Correct 16 ms 23848 KB Output is correct
7 Correct 14 ms 23816 KB Output is correct
8 Correct 14 ms 23800 KB Output is correct
9 Correct 14 ms 23844 KB Output is correct
10 Correct 13 ms 23756 KB Output is correct
11 Correct 15 ms 23912 KB Output is correct
12 Correct 18 ms 24092 KB Output is correct
13 Correct 25 ms 24112 KB Output is correct
14 Correct 20 ms 24200 KB Output is correct
15 Correct 20 ms 24204 KB Output is correct
16 Correct 18 ms 24012 KB Output is correct
17 Correct 18 ms 23968 KB Output is correct
18 Correct 17 ms 23984 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2280 ms 90252 KB Output is correct
2 Correct 2365 ms 90368 KB Output is correct
3 Correct 2270 ms 90256 KB Output is correct
4 Correct 2467 ms 90228 KB Output is correct
5 Correct 2327 ms 73880 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 30848 KB Output is correct
2 Correct 148 ms 30976 KB Output is correct
3 Correct 152 ms 28760 KB Output is correct
4 Correct 159 ms 28768 KB Output is correct
5 Correct 172 ms 28744 KB Output is correct
6 Correct 128 ms 28940 KB Output is correct
7 Correct 126 ms 28848 KB Output is correct
8 Correct 172 ms 28520 KB Output is correct
9 Correct 151 ms 27636 KB Output is correct
10 Correct 170 ms 28492 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23760 KB Output is correct
2 Correct 13 ms 23816 KB Output is correct
3 Correct 13 ms 23756 KB Output is correct
4 Correct 13 ms 23756 KB Output is correct
5 Correct 14 ms 23756 KB Output is correct
6 Correct 16 ms 23848 KB Output is correct
7 Correct 14 ms 23816 KB Output is correct
8 Correct 14 ms 23800 KB Output is correct
9 Correct 14 ms 23844 KB Output is correct
10 Correct 13 ms 23756 KB Output is correct
11 Correct 15 ms 23912 KB Output is correct
12 Correct 18 ms 24092 KB Output is correct
13 Correct 25 ms 24112 KB Output is correct
14 Correct 20 ms 24200 KB Output is correct
15 Correct 20 ms 24204 KB Output is correct
16 Correct 18 ms 24012 KB Output is correct
17 Correct 18 ms 23968 KB Output is correct
18 Correct 17 ms 23984 KB Output is correct
19 Correct 551 ms 37972 KB Output is correct
20 Correct 401 ms 37964 KB Output is correct
21 Correct 415 ms 38460 KB Output is correct
22 Correct 442 ms 38496 KB Output is correct
23 Correct 388 ms 38420 KB Output is correct
24 Correct 382 ms 34448 KB Output is correct
25 Correct 372 ms 34488 KB Output is correct
26 Correct 392 ms 34072 KB Output is correct
27 Correct 384 ms 34316 KB Output is correct
28 Correct 455 ms 34024 KB Output is correct
29 Correct 445 ms 33784 KB Output is correct
30 Correct 583 ms 33800 KB Output is correct
31 Correct 433 ms 33848 KB Output is correct
32 Correct 410 ms 33844 KB Output is correct
33 Correct 451 ms 33872 KB Output is correct
34 Correct 360 ms 33940 KB Output is correct
35 Correct 384 ms 33988 KB Output is correct
36 Correct 392 ms 33948 KB Output is correct
37 Correct 369 ms 33920 KB Output is correct
38 Correct 449 ms 33928 KB Output is correct
39 Correct 383 ms 34696 KB Output is correct
40 Correct 377 ms 32324 KB Output is correct
41 Correct 346 ms 33252 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23760 KB Output is correct
2 Correct 13 ms 23816 KB Output is correct
3 Correct 13 ms 23756 KB Output is correct
4 Correct 13 ms 23756 KB Output is correct
5 Correct 14 ms 23756 KB Output is correct
6 Correct 16 ms 23848 KB Output is correct
7 Correct 14 ms 23816 KB Output is correct
8 Correct 14 ms 23800 KB Output is correct
9 Correct 14 ms 23844 KB Output is correct
10 Correct 13 ms 23756 KB Output is correct
11 Correct 15 ms 23912 KB Output is correct
12 Correct 18 ms 24092 KB Output is correct
13 Correct 25 ms 24112 KB Output is correct
14 Correct 20 ms 24200 KB Output is correct
15 Correct 20 ms 24204 KB Output is correct
16 Correct 18 ms 24012 KB Output is correct
17 Correct 18 ms 23968 KB Output is correct
18 Correct 17 ms 23984 KB Output is correct
19 Correct 2280 ms 90252 KB Output is correct
20 Correct 2365 ms 90368 KB Output is correct
21 Correct 2270 ms 90256 KB Output is correct
22 Correct 2467 ms 90228 KB Output is correct
23 Correct 2327 ms 73880 KB Output is correct
24 Correct 170 ms 30848 KB Output is correct
25 Correct 148 ms 30976 KB Output is correct
26 Correct 152 ms 28760 KB Output is correct
27 Correct 159 ms 28768 KB Output is correct
28 Correct 172 ms 28744 KB Output is correct
29 Correct 128 ms 28940 KB Output is correct
30 Correct 126 ms 28848 KB Output is correct
31 Correct 172 ms 28520 KB Output is correct
32 Correct 151 ms 27636 KB Output is correct
33 Correct 170 ms 28492 KB Output is correct
34 Correct 551 ms 37972 KB Output is correct
35 Correct 401 ms 37964 KB Output is correct
36 Correct 415 ms 38460 KB Output is correct
37 Correct 442 ms 38496 KB Output is correct
38 Correct 388 ms 38420 KB Output is correct
39 Correct 382 ms 34448 KB Output is correct
40 Correct 372 ms 34488 KB Output is correct
41 Correct 392 ms 34072 KB Output is correct
42 Correct 384 ms 34316 KB Output is correct
43 Correct 455 ms 34024 KB Output is correct
44 Correct 445 ms 33784 KB Output is correct
45 Correct 583 ms 33800 KB Output is correct
46 Correct 433 ms 33848 KB Output is correct
47 Correct 410 ms 33844 KB Output is correct
48 Correct 451 ms 33872 KB Output is correct
49 Correct 360 ms 33940 KB Output is correct
50 Correct 384 ms 33988 KB Output is correct
51 Correct 392 ms 33948 KB Output is correct
52 Correct 369 ms 33920 KB Output is correct
53 Correct 449 ms 33928 KB Output is correct
54 Correct 383 ms 34696 KB Output is correct
55 Correct 377 ms 32324 KB Output is correct
56 Correct 346 ms 33252 KB Output is correct
57 Correct 2677 ms 90456 KB Output is correct
58 Correct 2650 ms 90476 KB Output is correct
59 Correct 2885 ms 91288 KB Output is correct
60 Correct 2356 ms 91332 KB Output is correct
61 Correct 2342 ms 91260 KB Output is correct
62 Correct 2384 ms 91276 KB Output is correct
63 Correct 1862 ms 76772 KB Output is correct
64 Correct 1809 ms 76992 KB Output is correct
65 Correct 2033 ms 75124 KB Output is correct
66 Correct 2104 ms 75116 KB Output is correct
67 Correct 2099 ms 74940 KB Output is correct
68 Correct 2163 ms 74040 KB Output is correct
69 Correct 2131 ms 74076 KB Output is correct
70 Correct 2138 ms 74132 KB Output is correct
71 Correct 2136 ms 74152 KB Output is correct
72 Correct 2197 ms 74224 KB Output is correct
73 Correct 1631 ms 72352 KB Output is correct
74 Correct 1796 ms 72208 KB Output is correct
75 Correct 1670 ms 72396 KB Output is correct
76 Correct 2000 ms 72560 KB Output is correct
77 Correct 1951 ms 72216 KB Output is correct
78 Correct 2137 ms 77116 KB Output is correct
79 Correct 1534 ms 65532 KB Output is correct
80 Correct 1857 ms 70840 KB Output is correct