Official Solutions Presentation

We can view the temperatures as an array $v$. We want to decrement one contiguous interval by a value $d \le x$ such that the length of the longest increasing subsequence is longest possible.

Subtasks 1-3: Brute Force

One key observation is that it is useless to subtract $d$ from any interval $[l,r]$ as opposed to just $[1, r]$ for any $l \neq 1$. Additionally, observe that it is optimal to simply subtract $x$ from the interval $[1, r]$ instead of some other $d < x$.

An $\mathcal{O}(n^2 \log n)$ algorithm would involve brute forcing for all prefixes. Subtract $x$ from each interval $[1, i]$ for all $i \in \{1, 2, \dotsc, n\}$ and then find the LIS after each subtraction.

Subtask 4: One pass

Simply take the LIS of the array. Any $\mathcal{O}(n \log n)$ algorithm to find the LIS will pass.

General Solution

For each $i$, let $L_i$ be the length of the longest increasing subsequence ending at $i$ and $R_i$ be the length of the longest increasing subsequence starting at $i$ after $[1, i]$ is decremented. We can compute each $R_i$ by storing the length of the longest decreasing subsequence for each prefix of the reverse of the input array.

The final answer is $\max_{i \in \{0, 1, \dotsc, n\}} L_i+R_i-1$.

Implementation

In the implementation $L_i$ is $dp_i$ and $R_i-1$ is the variable $j$ on line $27$.

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll n, x, v[200005], dp[200005];

int main()
{
	cin >> n >> x;