oj.uz

Submission #519909

# Submission time Handle Problem Language Result Execution time Memory
519909 2022-01-27T16:07:50 Z arujbansal Rabbit Carrot (LMIO19_triusis) C++17
0 / 100
 1 ms 204 KB 
#include <bits/stdc++.h>

using namespace std;

const int MXN = 2e5 + 1;
const int SL = -1e9, SR = 1e9;

struct node {
	int val;
	node *lc, *rc;

	node() : lc(0), rc(0) {}
};

deque<node> buffer;

node* create_node() {
	buffer.emplace_back();
	return &buffer.back();
}

int query(node* &cur, int l, int r, int ql, int qr) {
	if (!cur) return 0;
	if (l > qr || r < ql) return 0;
	if (l >= ql && r <= qr) return cur->val;

	int mid = l + (r - l) / 2;
	return max(query(cur->lc, l, mid, ql, qr), query(cur->rc, mid + 1, r, ql, qr));
}

void maximise(node* &cur, int l, int r, int pos, int val) {
	if (!cur) cur = create_node();
	if (l == r) {
		cur->val = max(cur->val, val);
		return;
	}

	int mid = l + (r - l) / 2;
	if (pos <= mid) maximise(cur->lc, l, mid, pos, val);
	else maximise(cur->rc, mid + 1, r, pos, val);

	if (cur->lc) cur->val = max(cur->val, cur->lc->val);
	if (cur->rc) cur->val = max(cur->val, cur->rc->val);
}

int query(node* &root, int l) {
	return query(root, SL, SR, l, SR);
}

void maximise(node* &root, int pos, int val) {
	maximise(root, SL, SR, pos, val);
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int N, M;
	cin >> N >> M;

	node* root = create_node();
	// maximise(root, 0, 1);

	for (int i = 1; i <= N; i++) {
		int x;
		cin >> x;

		x -= i * M;

		maximise(root, x, query(root, x) + 1);
	}	

	cout << N - root->val;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -