All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Let's call arrays of the form x x+1 ... x+k nice. In other words nice arrays are arrays that form increasing arithmetic progression with the difference of one.
You are given an array of N integers. Let's denote it's numbers by a1, a2, ..., aN. You are also given M change queries. Every change query is a query of the form "X Y" with the meaning that the X-th number in it becomes equal to Y. We perform these queries one after another, strictly in this order. Please, calculate the length of the longest nice subarray of this array, i.e. the length of the longest segment [L; R] that (aL, aL+1, ... aR) is a nice array before all the queries and after every query.
The first line of input consists of two integers N and M, separated by a single space - the length of the array and the number of queries.
The second line of input consists of N integers, the i-th equals to ai - namely the i-th number in the array.
The following M lines contains the queries in the form "X Y", where X and Y are natural numbers with the meaning that the X-th number becomes equal to Y.
Output the length of the longest nice subarray of the initial array at the first line of output. Then, output M integers at separate lines. The i-th such line should contain the length of the longest nice subarray after the i-th changing query.
Anytime ai <= 2 * N holds.
Input: 5 5 1 4 3 5 2 2 2 4 4 5 5 3 7 4 8 Output: 1 3 4 5 2 2
1 <= N <= 100, 1 <= M <= 1000 : 20 points.
1 <= N, M <= 5000 : 26 points.
1 <= N, M <= 105 : 54 points.
|Tags||easy, greedy, ltime10, segment-tree, xcwgf666|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.