oj.uz

Submission #880964

# Submission time Handle Problem Language Result Execution time Memory
880964 2023-11-30T09:21:42 Z dubabuba Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
17 / 100
 762 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
#define ff first
#define ss second

void ono_max(int &MAX, int CMP) { if(CMP > MAX) MAX = CMP;}
void ono_min(int &MIN, int CMP) { if(CMP < MIN) MIN = CMP;}

int merge(
	vi &edit, const int &st, const int &en,
	const vi &L, const int &L_st, const int &L_en,
	const vi &R, const int &R_st, const int &R_en) {
	int ret = 0;

	int cur_L = L_st, cur_R = R_st;
	for(int i = st; i <= en; i++) {
		if(cur_L == L_en + 1) {
			edit[i] = R[cur_R];
			cur_R++;
			continue;
		}

		if(cur_R == R_en + 1) {
			edit[i] = L[cur_L];
			cur_L++;
			continue;
		}

		if(L[cur_L] <= R[cur_R]) {
			edit[i] = L[cur_L];
			cur_L++;
		}
		else {
			edit[i] = R[cur_R];
			ono_max(ret, R[cur_R]);
			cur_R++;
		}
	}
	return ret;
}

const int mxn = 5050;
vector<vi> tmp(2, vi (mxn));
vi t(mxn), a(mxn);
int n, m;

pii query(int lvl, int l, int r) {
	if(l == r) {
		tmp[lvl][l] = a[l];
		return {0, a[l]};
	}

	int m = (l + r) / 2;
	pii L_qr = query((lvl + 1) % 2, l, m);
	pii R_qr = query((lvl + 1) % 2, m + 1, r);
	int MX = merge(
			tmp[lvl], l, r,
			tmp[(lvl + 1) % 2], l, m,
			tmp[(lvl + 1) % 2], m + 1, r
		);

	int ans = 0;
	ono_max(ans, L_qr.ff);
	ono_max(ans, R_qr.ff);
	if(MX != 0) ono_max(ans, MX + L_qr.ss);
	return {ans, max(L_qr.ss, R_qr.ss)};
}

int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		cin >> a[i];

	while(m--) {
		int l, r, k;
		cin >> l >> r >> k;

		pii q = query(0, l, r);
		// cout << l << ' ' << r << ": " << q.ff << ' ';
		cout << (q.ff <= k) << '\n';
	}
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 6 ms 348 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 8 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 5 ms 348 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 6 ms 348 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 8 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 5 ms 348 KB Output is correct
11 Correct 99 ms 348 KB Output is correct
12 Correct 307 ms 604 KB Output is correct
13 Correct 376 ms 600 KB Output is correct
14 Correct 595 ms 652 KB Output is correct
15 Correct 631 ms 644 KB Output is correct
16 Correct 762 ms 604 KB Output is correct
17 Correct 339 ms 600 KB Output is correct
18 Correct 431 ms 596 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 1112 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 6 ms 348 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 8 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 5 ms 348 KB Output is correct
11 Correct 99 ms 348 KB Output is correct
12 Correct 307 ms 604 KB Output is correct
13 Correct 376 ms 600 KB Output is correct
14 Correct 595 ms 652 KB Output is correct
15 Correct 631 ms 644 KB Output is correct
16 Correct 762 ms 604 KB Output is correct
17 Correct 339 ms 600 KB Output is correct
18 Correct 431 ms 596 KB Output is correct
19 Runtime error 11 ms 1372 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 6 ms 348 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 8 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 5 ms 348 KB Output is correct
11 Correct 99 ms 348 KB Output is correct
12 Correct 307 ms 604 KB Output is correct
13 Correct 376 ms 600 KB Output is correct
14 Correct 595 ms 652 KB Output is correct
15 Correct 631 ms 644 KB Output is correct
16 Correct 762 ms 604 KB Output is correct
17 Correct 339 ms 600 KB Output is correct
18 Correct 431 ms 596 KB Output is correct
19 Runtime error 180 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -