Submission #481121

#	Time	Username	Problem	Language	Result	Execution time	Memory
481121		s_samchenko	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	197 ms	24292 KiB

triusis

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#define ll long long
#define ff first
#define ss second
#define int ll
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int inf = 1e15;
const int mod = 1e9+7;
const int N = 3e5+100;

struct segtree{
	int size;
	vector <int> t;
	
	segtree(int n){
		size = 1;
		while (size < n) size <<= 1;
		t.resize(2*size - 1);
	}
	
	void set(int i, int v, int x, int lx, int rx){
		if (rx - lx == 1){
			t[x] = v;
			return;
		}
		int m = (lx + rx) / 2;
		if (i < m) set(i, v, 2*x + 1, lx, m);
		else set(i, v, 2*x + 2, m, rx);
		t[x] = max(t[2*x + 1], t[2*x + 2]);
	}
	
	void set(int i, int v){
		set(i, v, 0, 0, size);
	}
	
	int get(int l, int r, int x, int lx, int rx){
		if (l >= rx || lx >= r) return 0;
		if (l <= lx && r >= rx) return t[x];
		int m = (lx + rx) / 2;
		return max(get(l, r, 2*x + 1, lx, m), get(l, r, 2*x + 2, m, rx));
	}
	
	
	int get(int l, int r){
		return get(l, r + 1, 0, 0, size);
	}
};

int longest_nondec_subseq(const vector<int>& seq) {
	vector<int> min_endings;
	for (int i : seq) {
		// note that we use upper_bound instead of lower_bound bc it just has to be nondecreasing
		int pos = std::upper_bound(min_endings.begin(), min_endings.end(), i) - min_endings.begin();
		// standard LIS protocol
		if (pos == min_endings.size()) {
			min_endings.push_back(i);
		} else {
			min_endings[pos] = i;
		}
	}
	return min_endings.size();
}

void solve(){
	int n, m;
	cin >> n >> m;
	vector <int> a(n+1);
	for (int i = 1; i <= n; ++i) cin >> a[i];
	vector <int> b;
	for (int i = 1; i <= n; ++i){
		if (a[i] > m * i) continue;
		b.pb(m * i - a[i]);
	}
	vector <int> c = b; sort(all(c));
	map <int, int> mp;
	for (int i = 0; i < b.size(); ++i)
		if (mp[c[i]] == 0) mp[c[i]] = i+1;
	
	vector <int> dp(n+100);
	segtree st(n+100);
	for (int i = 0; i < b.size(); ++i){
		dp[i] = st.get(0, mp[b[i]]) + 1;
		st.set(mp[b[i]], dp[i]);
	}
	cout << n - *max_element(all(dp));
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while (tt--){
		solve();
		cout << '\n';
	}
}

Compilation message (stderr)

triusis.cpp: In function 'long long int longest_nondec_subseq(const std::vector<long long int>&)':
triusis.cpp:60:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   if (pos == min_endings.size()) {
      |       ~~~~^~~~~~~~~~~~~~~~~~~~~
triusis.cpp: In function 'void solve()':
triusis.cpp:81:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  for (int i = 0; i < b.size(); ++i)
      |                  ~~^~~~~~~~~~
triusis.cpp:86:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for (int i = 0; i < b.size(); ++i){
      |                  ~~^~~~~~~~~~

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