Submission #1087158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087158		coldbr3w	Financial Report (JOI21_financial)	C++17	14 / 100	4050 ms	58228 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 3e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 350;
ll nxt[N], a[N], dp[N], st[N][20], tmp[N];
ll n,d;
ll get(ll l, ll r){
	ll p = 31 - __builtin_clz(r - l + 1);
	return min(st[l][p], st[r - (1 << p) + 1][p]);
}
ll get_nxt(ll l, ll r){
	ll p = 31 - __builtin_clz(r - l + 1);
	return max(st[l][p], st[r - (1 << p) + 1][p]);
}
void build(){
	for(int i = 1; i <= n;i++) st[i][0] = a[i];
	for(int j = 1; j <= 19;j++){
		for(int i = 1; i + (1 << j) <= n + 1;i++) st[i][j] = min(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
	}
	for(int i = 1; i <= n;i++) tmp[i] = (i + d > n ? inf : get(i, i + d));
	for(int i = 1; i <= n;i++) st[i][0] = tmp[i];
	for(int j = 1; j <= 19;j++){
		for(int i = 1; i + (1 << j) <= n + 1;i++) st[i][j] = max(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
	}
	for(int i = 1; i + d <= n;i++){
		ll l = i + d, r = n;
		while(l <= r){
			ll mid = (l + r) / 2;
			if(get_nxt(i, mid - d) <= a[i]) nxt[i] = mid, l = mid + 1;
			else r = mid - 1;
		}
	}
	for(int i = 1; i <= n;i++) if(i + d > n) nxt[i] = n;
}
void to_thic_cau(){
	cin >> n >> d;
	for(int i = 1; i <= n;i++) cin >> a[i];
	build();
	ll res = 0;
	for(int i = 1; i <= n;i++){
		dp[i] = 1;
		for(int j = 1; j <= i - 1;j++) if(a[i] > a[j] && nxt[j] >= i) dp[i] = max(dp[i], dp[j] + 1);
		res = max(res, dp[i]);
	}
	cout << res << '\n';
}

signed main()   
{ 
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35