oj.uz

답안 #548297

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
548297 2022-04-13T00:31:41 Z PikaQ Rabbit Carrot (LMIO19_triusis) C++17
0 / 100
 1 ms 1876 KB 
#include<bits/stdc++.h>
#define int ll
#define forn(i,n) for(int i=0;i<(n);i++)
#define Forn(i,n) for(int i=1;i<=(n);i++)
#define ll long long
#define pb push_back
#define F first
#define S second
#define vi vector<long long>
#define pii pair<int,int>
#define all(p) p.begin(),p.end()
#define st0(p) memset((p),0,sizeof(p))
#define sz(x) (x).size()
#define rz resize
using namespace std;

 
inline void USACO(string filename){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}
 
void debug() {cout << endl;}
template <class T, class ...U> void debug(T a, U ... b) { cerr << a << " "; debug(b...);}
const int N = (int) 2e5+9;
const int INF = (int) 1e9 + 7;
int n,k;
struct FenwickTree{
	int t[N];
	void init(){
		for(auto &i : t) i = -INF;
	}
	void modify(int p,int v){
		for(;p <= n+1;p++){
			t[p] = max(t[p],v);
		}
	}
	int query(int p){
		int res = -INF;
		for(;p;p-=(p&-p)) res = max(res,t[p]);
		return res;
	}
}bit;
void solve(){	
	cin >> n >> k;
	vi a(n);
	forn(i,n) cin >> a[i];
	for(int i = 1;i <= n;i++){
		a[i-1] -= k * i;
		a[i-1] *= -1;
	}
	for(auto &i : a) cout << i << '\n';
	vi dp(n);
	vi rk = a;
	rk.pb(0);
	sort(all(rk));
	rk.resize(unique(all(rk)) - rk.begin());
	forn(i,n){
		a[i] = upper_bound(all(rk),a[i]) - rk.begin();
	}
	bit.init();
	bit.modify(upper_bound(all(rk),0)-rk.begin(),0);
	forn(i,n){
		dp[i] = bit.query(a[i]) + 1;
		bit.modify(a[i],dp[i]);
	}
	cout << n - bit.query(n+1) << '\n';
}

signed main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	solve();
	return 0;
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1876 KB Output isn't correct
2 Halted 0 ms 0 KB -