Submission #944204

#	Time	Username	Problem	Language	Result	Execution time	Memory
944204		Sunbae	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	45 ms	6196 KiB

triusis

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;
ll a[N];
vector<ll>C;
int m, bit[N];
void upd(int i, int val){
	for(; i<=m; i+=i&-i) bit[i] = max(bit[i], val);
}
int qry(int i){
	int res = 0;
	for(; i; i-=i&-i) res = max(res, bit[i]);
	return res;
} 
int pos(ll x){
	return upper_bound(C.begin(), C.end(), x) - C.begin();
}
signed main(){
	int n; ll M; scanf("%d %lld", &n, &M);
	for(int i = 1; i<=n; ++i) scanf("%lld", a+i), C.push_back(M*i - a[i]);
	sort(C.begin(), C.end()); C.resize(unique(C.begin(), C.end()) - C.begin()); m = C.size();
	int LIS = 0;
	for(int i = 1; i<=n; ++i){
		ll b = M*i - a[i];
		if(b >= 0){
			int ind = pos(b), T = qry(ind) + 1;
			LIS = max(T, LIS);
			upd(ind, T);
		}
	}
	printf("%d", n - LIS);
}

Compilation message (stderr)

triusis.cpp: In function 'int main()':
triusis.cpp:20:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  int n; ll M; scanf("%d %lld", &n, &M);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~
triusis.cpp:21:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  for(int i = 1; i<=n; ++i) scanf("%lld", a+i), C.push_back(M*i - a[i]);
      |                            ~~~~~^~~~~~~~~~~~~

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