oj.uz

Submission #481117

# Submission time Handle Problem Language Result Execution time Memory
481117 2021-10-19T13:50:03 Z s_samchenko Rabbit Carrot (LMIO19_triusis) C++17
0 / 100
 0 ms 204 KB 
#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);
	}
};

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(n+1);
	for (int i = 1; i <= n; ++i){
		b[i] = m * i - a[i];
	}
	vector <int> c = b; sort(all(c));
	map <int, int> mp;
	for (int i = 0; i <= n; ++i)
		if (mp[c[i]] == 0) mp[c[i]] = i;
	
	vector <int> dp(n+100);
	segtree st(n+100);
	for (int i = 1; i <= n; ++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';
	}
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -