제출 #947381

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
947381		oblantis	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	226 ms	23992 KiB

triusis

//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 2e5 + 12;
int tr[maxn * 4], it, x;
void upd(int v, int l, int r){
	if(l + 1 == r){
		tr[v] = x;
		return;
	}
	if((l + r) / 2 <= it)upd(v * 2 + 2, (l + r) / 2, r);
	else upd(v * 2 + 1, l, (l + r) / 2);
	tr[v] = max(tr[v * 2 + 1], tr[v * 2 + 2]);
}
int get(int v, int l, int r){
	if(r - 1 <= it)return tr[v];
	if(it < l)return 0;
	return max(get(v * 2 + 1, l, (l + r) / 2), get(v * 2 + 2, (l + r) / 2, r));
}
void solve() {
	int n, k, cnt = 0;
	cin >> n >> k;
	int a[n];
	set<int> s;
	map<int, int> m;
	s.insert(0);
	for(int i = 0; i < n; i++){
		cin >> a[i];
		a[i] = a[i] - (i + 1) * k;
		s.insert(a[i]);
	}
	for(auto i : s)m[i] = cnt++;
	for(int i = n - 1; i >= 0; i--){
		a[i] = m[a[i]];
		it = a[i];
		x = get(0, 0, cnt) + 1;
		upd(0, 0, cnt);
	}
	it = m[0];
	cout << n - get(0, 0, cnt);
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int times = 1;
	//cin >> times;
	for(int i = 1; i <= times; i++) {
		solve();
	}
	return 0;
}

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