oj.uz

Submission #880969

# Submission time Handle Problem Language Result Execution time Memory
880969 2023-11-30T09:37:50 Z dubabuba Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
17 / 100
 3000 ms 42876 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 >> 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 15952 KB Output is correct
3 Correct 7 ms 15896 KB Output is correct
4 Correct 5 ms 15892 KB Output is correct
5 Correct 5 ms 16148 KB Output is correct
6 Correct 11 ms 15896 KB Output is correct
7 Correct 11 ms 15896 KB Output is correct
8 Correct 11 ms 16120 KB Output is correct
9 Correct 7 ms 15896 KB Output is correct
10 Correct 11 ms 15892 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 15952 KB Output is correct
3 Correct 7 ms 15896 KB Output is correct
4 Correct 5 ms 15892 KB Output is correct
5 Correct 5 ms 16148 KB Output is correct
6 Correct 11 ms 15896 KB Output is correct
7 Correct 11 ms 15896 KB Output is correct
8 Correct 11 ms 16120 KB Output is correct
9 Correct 7 ms 15896 KB Output is correct
10 Correct 11 ms 15892 KB Output is correct
11 Correct 102 ms 16108 KB Output is correct
12 Correct 311 ms 15892 KB Output is correct
13 Correct 367 ms 16140 KB Output is correct
14 Correct 618 ms 15892 KB Output is correct
15 Correct 615 ms 16092 KB Output is correct
16 Correct 749 ms 16108 KB Output is correct
17 Correct 325 ms 16100 KB Output is correct
18 Correct 422 ms 16104 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2619 ms 42872 KB Output is correct
2 Correct 2695 ms 42728 KB Output is correct
3 Execution timed out 3028 ms 42876 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 218 ms 20488 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 15952 KB Output is correct
3 Correct 7 ms 15896 KB Output is correct
4 Correct 5 ms 15892 KB Output is correct
5 Correct 5 ms 16148 KB Output is correct
6 Correct 11 ms 15896 KB Output is correct
7 Correct 11 ms 15896 KB Output is correct
8 Correct 11 ms 16120 KB Output is correct
9 Correct 7 ms 15896 KB Output is correct
10 Correct 11 ms 15892 KB Output is correct
11 Correct 102 ms 16108 KB Output is correct
12 Correct 311 ms 15892 KB Output is correct
13 Correct 367 ms 16140 KB Output is correct
14 Correct 618 ms 15892 KB Output is correct
15 Correct 615 ms 16092 KB Output is correct
16 Correct 749 ms 16108 KB Output is correct
17 Correct 325 ms 16100 KB Output is correct
18 Correct 422 ms 16104 KB Output is correct
19 Incorrect 494 ms 28940 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 15952 KB Output is correct
3 Correct 7 ms 15896 KB Output is correct
4 Correct 5 ms 15892 KB Output is correct
5 Correct 5 ms 16148 KB Output is correct
6 Correct 11 ms 15896 KB Output is correct
7 Correct 11 ms 15896 KB Output is correct
8 Correct 11 ms 16120 KB Output is correct
9 Correct 7 ms 15896 KB Output is correct
10 Correct 11 ms 15892 KB Output is correct
11 Correct 102 ms 16108 KB Output is correct
12 Correct 311 ms 15892 KB Output is correct
13 Correct 367 ms 16140 KB Output is correct
14 Correct 618 ms 15892 KB Output is correct
15 Correct 615 ms 16092 KB Output is correct
16 Correct 749 ms 16108 KB Output is correct
17 Correct 325 ms 16100 KB Output is correct
18 Correct 422 ms 16104 KB Output is correct
19 Correct 2619 ms 42872 KB Output is correct
20 Correct 2695 ms 42728 KB Output is correct
21 Execution timed out 3028 ms 42876 KB Time limit exceeded
22 Halted 0 ms 0 KB -