제출 #519912

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
519912		arujbansal	Rabbit Carrot (LMIO19_triusis)	C++17	0 / 100	1 ms	204 KiB

triusis

#include <bits/stdc++.h>

using namespace std;

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

struct node {
	int val = -INF;
	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 + 1) - root->val;
}

컴파일 시 표준 에러 (stderr) 메시지

triusis.cpp:5:32: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+19' to '2147483647' [-Woverflow]
    5 | const int MXN = 2e5 + 1, INF = 1e19;
      |                                ^~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37