oj.uz

Submission #715589

# Submission time Handle Problem Language Result Execution time Memory
715589 2023-03-27T09:18:06 Z amunduzbaev Rabbit Carrot (LMIO19_triusis) C++17
0 / 100
 4 ms 6484 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long ll;
#define int ll

const int N = 2e5 + 5;
int a[N], dp[N];

struct ST{
	int tree[N << 2];
	ST(){
		memset(tree, 200, sizeof tree);
	}
	
	void set(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = max(tree[x], v); return; }
		int m = (lx + rx) >> 1;
		if(i <= m) set(i, v, lx, m, x << 1);
		else set(i, v, m + 1, rx, x << 1 | 1);
		tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
	}
	
	int get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -N;
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
	}
}tree;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);

	int n, m; cin >> n >> m;
	vector<int> t;
	t.push_back(0);
	for(int i=1;i<=n;i++){
		cin >> a[i];
		a[i] -= i * m;
		t.push_back(a[i]);
	}
	sort(t.begin(), t.end());
	t.erase(unique(t.begin(), t.end()), t.end());
	{
		int j = lower_bound(t.begin(), t.end(), a[0]) - t.begin();
		tree.set(j, 0);
	}
	for(int i=1;i<=n;i++){
		int j = lower_bound(t.begin(), t.end(), a[i]) - t.begin();
		cout<<j<<endl;
		dp[i] = tree.get(j, n) + 1;
		tree.set(j, dp[i]);
	}
	
	cout<<n - tree.get(0, n)<<"\n";
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6484 KB Output isn't correct
2 Halted 0 ms 0 KB -