oj.uz

Submission #880990

# Submission time Handle Problem Language Result Execution time Memory
880990 2023-11-30T10:11:23 Z dubabuba Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 3000 ms 47956 KB 
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
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 mxl = 25;
const int mxn = 2e5 + 10;
vector<vi> sus(mxl, vi (mxn));
vector<vi> tmp(mxl, vi (mxn));
vi a(mxn), t(mxn);
int n, m;


struct tree {
	int tl, tr;
	int mxx, ans;
	vi &range = t;

	tree *LC, *RC;

	tree() {tl = tr = 0, mxx = ans = 0;}
	tree(int lvl, int l, int r) {
		tl = l, tr = r;
		range = sus[lvl];
		ans = mxx = 0;
	}

	friend tree *comb(const tree *L, const tree *R) {
		tree *ret = new tree();
		ret-> ans = max(L-> ans, R-> ans);
		ret-> mxx = max(L-> mxx, R-> mxx);
		ret-> tl = L-> tl;
		ret-> tr = R-> tr;

		int q = merge(
				ret->range, L-> tl, R-> tr,
				L-> range, L-> tl, L-> tr,
				R-> range, R-> tl, R-> tr
			);
		if(q != 0) ono_max(ret-> ans, L-> mxx + q);
		return ret;
	}

	void build(int lvl) {
		if(tl == tr) {
			ans = range[tl] = a[tl];
			mxx = 0;
			return;
		}

		LC = new tree(lvl + 1, tl, (tl + tr) / 2);
		RC = new tree(lvl + 1, (tl + tr) / 2 + 1, tr);
		LC-> build(lvl + 1);
		RC-> build(lvl + 1);

		tree *buba = comb(LC, RC);
		ans = buba-> ans;
		mxx = buba-> mxx;
	}

	tree *query(int l, int r) {
		if(tl == l && r == tr) return this;
		if(r <= LC-> tr) return LC-> query(l, r);
		if(RC-> tl <= l) return RC-> query(l, r);

		tree *L_qr = LC-> query(l, LC-> tr);
		tree *R_qr = RC-> query(RC-> tl, r);
		tree *ret = comb(L_qr, R_qr);
		return ret;
	}
};

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

	tree *root = new tree(0, 1, n);
	root-> build(0);

	while(m--) {
		int l, r, k;
		cin >> l >> r >> k;
		tree *q = root-> query(l, r);
		cout << (q-> ans <= k) << '\n';
	}
	return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 41292 KB Output is correct
2 Correct 22 ms 41036 KB Output is correct
3 Incorrect 26 ms 41280 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 41292 KB Output is correct
2 Correct 22 ms 41036 KB Output is correct
3 Incorrect 26 ms 41280 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3013 ms 47204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3089 ms 47956 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 41292 KB Output is correct
2 Correct 22 ms 41036 KB Output is correct
3 Incorrect 26 ms 41280 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 41292 KB Output is correct
2 Correct 22 ms 41036 KB Output is correct
3 Incorrect 26 ms 41280 KB Output isn't correct
4 Halted 0 ms 0 KB -