oj.uz

Submission #1005520

# Submission time Handle Problem Language Result Execution time Memory
1005520 2024-06-22T14:36:32 Z ByeWorld Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
34 / 100
 611 ms 262144 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define ll long long
// #define int long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii, int> ipii;
const int MAXN = 1e6+10;
const int INF = 1e9+10;
const int LOG = 29;
const int MOD = 1e9+7;
const int SQRT = 450;
const vector<int> NOL = {};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};

int n, m, q;
int a[MAXN];

struct seg {
	set <int> st[3*MAXN]; int val[3*MAXN];
	void mrg(int id){
		for(auto in : st[lf]) st[id].insert(in);
		for(auto in : st[rg]) st[id].insert(in);
		val[id] = max(val[lf], val[rg]);

		int le = *(--st[lf].end());
		auto it = st[rg].lower_bound(le);
		if(it != st[rg].begin()){
			it--; 
			val[id] = max(val[id], le + *(it));
		}
	}
	void bd(int id, int l, int r){
		if(l==r){ st[id].insert(a[l]); val[id] = -INF; return; }
		bd(lf, l, md); bd(rg, md+1, r);
		mrg(id);
	}
	int que(int id, int l, int r, int x, int y){
		if(r<x || y<l) return -INF;
		if(x<=l && r<=y) return *(--st[id].end());
		return max(que(lf, l, md, x, y), que(rg, md+1, r, x, y));
	}
	int find(int id, int l, int r, int x, int y){
		if(r<x || y<l) return -INF;
		if(x<=l && r<=y){
			int bef = que(1, 1, n, x, l-1); // mx di sebelum
			int aft = -INF;
			auto it = st[id].lower_bound(bef);
			if(it != st[id].begin()){
				it--; 
				aft = *(it);
			}

			return max(val[id], bef+aft);
		}
		int MX = max(find(lf, l, md, x, y), find(rg, md+1, r, x, y));

		// int bef = que(1, 1, n, x, l-1), aft = -INF;
		// auto it = st[rg].lower_bound(bef);
		// if(it != st[rg].begin()){
		// 	it--; 
		// 	aft = *(it);
		// }
		return MX;
	}
} A;

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i=1; i<=n; i++) cin >> a[i];
	A.bd(1, 1, n);

	for(int xx=1; xx<=m; xx++){
		int l, r, x; cin >> l >> r >> x;
		cout << (A.find(1, 1, n, l, r) <= x) << '\n';
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 144216 KB Output is correct
2 Correct 23 ms 144220 KB Output is correct
3 Correct 24 ms 144220 KB Output is correct
4 Correct 24 ms 144288 KB Output is correct
5 Correct 20 ms 144220 KB Output is correct
6 Correct 23 ms 144484 KB Output is correct
7 Correct 24 ms 144476 KB Output is correct
8 Correct 22 ms 144388 KB Output is correct
9 Correct 23 ms 144216 KB Output is correct
10 Correct 22 ms 144220 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 144216 KB Output is correct
2 Correct 23 ms 144220 KB Output is correct
3 Correct 24 ms 144220 KB Output is correct
4 Correct 24 ms 144288 KB Output is correct
5 Correct 20 ms 144220 KB Output is correct
6 Correct 23 ms 144484 KB Output is correct
7 Correct 24 ms 144476 KB Output is correct
8 Correct 22 ms 144388 KB Output is correct
9 Correct 23 ms 144216 KB Output is correct
10 Correct 22 ms 144220 KB Output is correct
11 Correct 27 ms 144984 KB Output is correct
12 Correct 34 ms 147460 KB Output is correct
13 Correct 35 ms 147292 KB Output is correct
14 Correct 47 ms 147176 KB Output is correct
15 Correct 39 ms 147328 KB Output is correct
16 Correct 34 ms 147284 KB Output is correct
17 Correct 31 ms 146516 KB Output is correct
18 Correct 27 ms 144732 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 284 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 611 ms 198704 KB Output is correct
2 Correct 549 ms 198812 KB Output is correct
3 Correct 301 ms 156436 KB Output is correct
4 Correct 290 ms 156496 KB Output is correct
5 Correct 272 ms 156496 KB Output is correct
6 Correct 299 ms 156500 KB Output is correct
7 Correct 300 ms 156496 KB Output is correct
8 Correct 211 ms 155996 KB Output is correct
9 Correct 79 ms 144476 KB Output is correct
10 Correct 217 ms 155732 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 144216 KB Output is correct
2 Correct 23 ms 144220 KB Output is correct
3 Correct 24 ms 144220 KB Output is correct
4 Correct 24 ms 144288 KB Output is correct
5 Correct 20 ms 144220 KB Output is correct
6 Correct 23 ms 144484 KB Output is correct
7 Correct 24 ms 144476 KB Output is correct
8 Correct 22 ms 144388 KB Output is correct
9 Correct 23 ms 144216 KB Output is correct
10 Correct 22 ms 144220 KB Output is correct
11 Correct 27 ms 144984 KB Output is correct
12 Correct 34 ms 147460 KB Output is correct
13 Correct 35 ms 147292 KB Output is correct
14 Correct 47 ms 147176 KB Output is correct
15 Correct 39 ms 147328 KB Output is correct
16 Correct 34 ms 147284 KB Output is correct
17 Correct 31 ms 146516 KB Output is correct
18 Correct 27 ms 144732 KB Output is correct
19 Runtime error 225 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 144216 KB Output is correct
2 Correct 23 ms 144220 KB Output is correct
3 Correct 24 ms 144220 KB Output is correct
4 Correct 24 ms 144288 KB Output is correct
5 Correct 20 ms 144220 KB Output is correct
6 Correct 23 ms 144484 KB Output is correct
7 Correct 24 ms 144476 KB Output is correct
8 Correct 22 ms 144388 KB Output is correct
9 Correct 23 ms 144216 KB Output is correct
10 Correct 22 ms 144220 KB Output is correct
11 Correct 27 ms 144984 KB Output is correct
12 Correct 34 ms 147460 KB Output is correct
13 Correct 35 ms 147292 KB Output is correct
14 Correct 47 ms 147176 KB Output is correct
15 Correct 39 ms 147328 KB Output is correct
16 Correct 34 ms 147284 KB Output is correct
17 Correct 31 ms 146516 KB Output is correct
18 Correct 27 ms 144732 KB Output is correct
19 Runtime error 284 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -