oj.uz

Submission #880970

# Submission time Handle Problem Language Result Execution time Memory
880970 2023-11-30T09:38:29 Z dubabuba Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
30 / 100
 852 ms 43288 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 = 1e6 + 10;
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)};
}

struct node {
	int mx, mn;
	bool flag;
} st[mxn * 4];

void build(int id, int tl, int tr) {
	if(tl == tr) {
		st[id].mn = a[tl];
		st[id].mx = a[tr];
		st[id].flag = 1;
		return;
	}

	int tm = (tl + tr) / 2;
	build(id * 2 + 1, tl, tm);
	build(id * 2 + 2, tm + 1, tr);

	st[id].mx = max(st[id * 2 + 1].mx, st[id * 2 + 2].mx);
	st[id].mn = min(st[id * 2 + 1].mn, st[id * 2 + 2].mn);
	st[id].flag = 1;

	if(!st[id * 2 + 1].flag) st[id].flag = 0;
	if(!st[id * 2 + 2].flag) st[id].flag = 0;
	if(st[id * 2 + 1].mx > st[id * 2 + 2].mn)
		st[id].flag = 0;
}

node query(int id, int tl, int tr, int l, int r) {
	if(tl == l && r == tr) return st[id];
	int tm = (tl + tr) / 2;
	if(r <= tm) return query(id * 2 + 1, tl, tm, l, r);
	if(tm < l) return query(id * 2 + 2, tm + 1, tr, l, r);

	node L_qr = query(id * 2 + 1, tl, tm, l, tm);
	node R_qr = query(id * 2 + 2, tm + 1, tr, tm + 1, r);
	node ret; ret.flag = 1;

	ret.mx = max(L_qr.mx, R_qr.mx);
	ret.mn = min(L_qr.mn, R_qr.mn);
	if(!L_qr.flag) ret.flag = 0;
	if(!R_qr.flag) ret.flag = 0;
	if(L_qr.mx > R_qr.mn) ret.flag = 0;
	return ret;
}

int main() {
	cin.tie(0)-> sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		cin >> a[i];

	if(n >= 5050) build(0, 1, n);

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

		if(n < 5050) {
			pii q = query(0, l, r);
			cout << (q.ff <= k) << '\n';
		} else {
			node q = query(0, 1, n, l, r);
			cout << q.flag << '\n';
		}
	}
	return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15896 KB Output is correct
2 Correct 5 ms 15896 KB Output is correct
3 Correct 6 ms 15952 KB Output is correct
4 Correct 6 ms 15896 KB Output is correct
5 Correct 6 ms 15896 KB Output is correct
6 Correct 9 ms 15896 KB Output is correct
7 Correct 10 ms 15896 KB Output is correct
8 Correct 10 ms 16136 KB Output is correct
9 Correct 7 ms 15896 KB Output is correct
10 Correct 9 ms 15896 KB Output is correct
11 Correct 92 ms 16120 KB Output is correct
12 Correct 299 ms 16148 KB Output is correct
13 Correct 370 ms 16112 KB Output is correct
14 Correct 577 ms 16116 KB Output is correct
15 Correct 602 ms 16116 KB Output is correct
16 Correct 725 ms 16120 KB Output is correct
17 Correct 320 ms 16116 KB Output is correct
18 Correct 407 ms 15896 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 819 ms 43144 KB Output is correct
2 Correct 801 ms 42896 KB Output is correct
3 Correct 852 ms 42968 KB Output is correct
4 Correct 834 ms 43288 KB Output is correct
5 Correct 822 ms 42828 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 20568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15896 KB Output is correct
2 Correct 5 ms 15896 KB Output is correct
3 Correct 6 ms 15952 KB Output is correct
4 Correct 6 ms 15896 KB Output is correct
5 Correct 6 ms 15896 KB Output is correct
6 Correct 9 ms 15896 KB Output is correct
7 Correct 10 ms 15896 KB Output is correct
8 Correct 10 ms 16136 KB Output is correct
9 Correct 7 ms 15896 KB Output is correct
10 Correct 9 ms 15896 KB Output is correct
11 Correct 92 ms 16120 KB Output is correct
12 Correct 299 ms 16148 KB Output is correct
13 Correct 370 ms 16112 KB Output is correct
14 Correct 577 ms 16116 KB Output is correct
15 Correct 602 ms 16116 KB Output is correct
16 Correct 725 ms 16120 KB Output is correct
17 Correct 320 ms 16116 KB Output is correct
18 Correct 407 ms 15896 KB Output is correct
19 Incorrect 131 ms 22776 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15896 KB Output is correct
2 Correct 5 ms 15896 KB Output is correct
3 Correct 6 ms 15952 KB Output is correct
4 Correct 6 ms 15896 KB Output is correct
5 Correct 6 ms 15896 KB Output is correct
6 Correct 9 ms 15896 KB Output is correct
7 Correct 10 ms 15896 KB Output is correct
8 Correct 10 ms 16136 KB Output is correct
9 Correct 7 ms 15896 KB Output is correct
10 Correct 9 ms 15896 KB Output is correct
11 Correct 92 ms 16120 KB Output is correct
12 Correct 299 ms 16148 KB Output is correct
13 Correct 370 ms 16112 KB Output is correct
14 Correct 577 ms 16116 KB Output is correct
15 Correct 602 ms 16116 KB Output is correct
16 Correct 725 ms 16120 KB Output is correct
17 Correct 320 ms 16116 KB Output is correct
18 Correct 407 ms 15896 KB Output is correct
19 Correct 819 ms 43144 KB Output is correct
20 Correct 801 ms 42896 KB Output is correct
21 Correct 852 ms 42968 KB Output is correct
22 Correct 834 ms 43288 KB Output is correct
23 Correct 822 ms 42828 KB Output is correct
24 Incorrect 73 ms 20568 KB Output isn't correct
25 Halted 0 ms 0 KB -