제출 #948415

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

triusis

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MAX_A = 5e3;

template<typename T>
struct segtree {
	T size;
	vector<T> val;
	T id = 1e9;

	segtree(T n) {
		size = 1;
		while (size < n) {
			size *= 2;
		}
		val.assign(size * 2, id);
	}

	void update(T i, T v, T x, T lx, T rx) {
		if (rx - lx == 1) {
			val[x] = v;
			return;
		}
		T mid = (lx + rx) / 2;
		if (i < mid) {
			update(i, v, 2 * x + 1, lx, mid);
		} else {
			update(i, v, 2 * x + 2, mid, rx);
		}
		val[x] = max(val[2 * x + 1], val[2 * x + 2]);
	}

	void update(T i, T v) {
		update(i, v, 0, 0, size);
	}

	T query(T l, T r, T x, T lx, T rx) {
		if (r <= lx || l >= rx) {
			return id;
		}
		if (lx >= l && rx <= r) {
			return val[x];
		}
		T mid = (lx + rx) / 2;
		T calc1 = query(l, r, 2 * x + 1, lx, mid);
		T calc2 = query(l, r, 2 * x + 2, mid, rx);
		return max(calc1, calc2);
	}

	T query(T l, T r) {
		if (l == r) {
			return id;
		}
		return query(l, r, 0, 0, size);
	}
};


int solve() {
	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		a[i] -= i * m;
	}
	vector<int> sorted(a);
	sort(sorted.begin(), sorted.end());
	int at = 0;
	map<int, int> coord_comp;
	for (int i: sorted) {
		if (!coord_comp.count(i)) { coord_comp[i] = at++; }
	}
	// cmp(i) gives the compressed version of index i
	auto cmp = [&](int i) -> int { return coord_comp[a[i]]; };

	segtree<int> dp(coord_comp.size());
	dp.update(cmp(0), 1);
	for (int i = 1; i < a.size(); i++) {
		int max_prev = dp.query(cmp(i), coord_comp.size());
		if (max_prev != 1e9) {
			dp.update(cmp(i), max_prev + 1);
		} else {
			dp.update(cmp(i), 1);
		}
	}

	cout << dp.query(0, coord_comp.size());

	return 0;
}

#ifndef MY_UNIT_TEST

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
}

#endif

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

triusis.cpp: In function 'int solve()':
triusis.cpp:83:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for (int i = 1; i < a.size(); i++) {
      |                  ~~^~~~~~~~~~

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