Official Analysis

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. Note that we don't need to consider incrementing as well because every interval's decrease corresponds to another interval's increase.

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 always subtract $x$ from the interval $[1, r]$ no matter what.

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

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 that ends at and contains $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 $pref_longest_i$ and $R_i-1$ is the variable $pos$ in the second for loop.

Copy
#include <bits/stdc++.h>
using namespace std;

int temps[200005];
int pref_longest[200005];

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

Copy
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * this code here treats the change as incrementing the suffix instead of
 * decrementing the prefix as in the editorial but it's basically the same thing
 */
public class glo {

Copy
"""
this code here treats the change as incrementing the suffix instead of
decrementing the prefix as in the editorial but it's basically the same thing
"""
from bisect import bisect_left

temp_num, max_cheating = [int(i) for i in input().split()]
temps = [int(i) for i in input().split()]
assert temp_num == len(temps)