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\ne 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,\dots ,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,\dots ,n\}}{L}_i+R_i-1$.

Implementation

In the implementation $L_i$ is $d{p}_i$ and $R_i-1$ is the variable $j$ on line $27$.

1#include <bits/stdc++.h>
2#define ll long long
3
4using namespace std;
5
6ll n, x, v[200005], dp[200005];
7
8int main()
9{
10    cin >> n >> x;