CSES - Datatähti 2021 alku - Results
Submission details
Task:Alitaulukot
Sender:T
Submission time:2020-09-28 02:02:19 +0300
Language:Java
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.08 s1, 2, 3details
#20.08 s1, 2, 3details
#3ACCEPTED0.08 s1, 2, 3details
#40.08 s1, 2, 3details
#5ACCEPTED0.08 s1, 2, 3details
#6ACCEPTED0.10 s2, 3details
#70.10 s2, 3details
#80.10 s2, 3details
#90.10 s2, 3details
#10ACCEPTED0.10 s2, 3details
#110.26 s3details
#120.26 s3details
#130.28 s3details
#140.37 s3details
#150.30 s3details
#160.68 s3details
#170.67 s3details

Code

import java.util.*;
import java.io.*;
/**
 * Datatahti 2021 alku
 * Alitaulukot/Subtables
 * @author TRS
 */
public class Alitaulukot {
	//Constants
	static final int infinity = 0x3f3f3f3f;
	static final long linfinity = 0x3f3f3f3f3f3f3f3fL;
	static final int MOD = 1000000007;
	//Input
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	public static void main(String[] args) throws IOException {
		int n = readInt();
		int k = readInt();
		int[] array = new int[n];
		for (int i = 0; i < n; i++) {
			array[i] = readInt();
		}
		System.out.println(solve(array, k + 1));
	}
	static int solve(int[] array, int k) {
		int answer = 0;
		int i = 0;
		int minimum = array[0];
		int maximum = array[0];
		List<Integer> ascend = new ArrayList<Integer>();
		List<Integer> descend = new ArrayList<Integer>();
		ascend.add(0);
		descend.add(0);
		for (int j = 1; j < array.length; j++) {
			int value = array[j];
			while (ascend.size() > 0 && array[ascend.get(ascend.size() - 1)] > value) {
				ascend.remove(ascend.size() - 1);
			}
			while (descend.size() > 0 && array[descend.get(descend.size() - 1)] < value) {
				descend.remove(descend.size() - 1);
			}
			ascend.add(j);
			descend.add(j);
			if (array[j] > maximum) {
				maximum = array[j];
				if (maximum - minimum >= k) {
					while (maximum - array[ascend.get(0)] >= k) {
						ascend.remove(0);
					}
					i = ascend.get(0);
					minimum = array[i];
					while (descend.get(0) < i) {
						descend.remove(0);
					}
				}
			}
			else if (array[j] < minimum) {
				minimum = array[j];
				if (maximum - minimum >= k) {
					while (array[descend.get(0)] - minimum >= k) {
						descend.remove(0);
					}
					i = descend.get(0);
					maximum = array[i];
					while (ascend.get(0) < i) {
						ascend.remove(0);
					}
				}
			}
			answer += j - i + 1;
		}
		answer++;
		return answer;
	}
	static String next() throws IOException {
		while (st == null || !st.hasMoreTokens()) {
			st = new StringTokenizer(br.readLine().trim());
		}
		return st.nextToken();
	}
	static long readLong() throws IOException {
		return Long.parseLong(next());
	}
	static int readInt() throws IOException {
		return Integer.parseInt(next());
	}
	static double readDouble() throws IOException {
		return Double.parseDouble(next());
	}
	static char readCharacter() throws IOException {
		return next().charAt(0);
	}
	static String readLine() throws IOException {
		return br.readLine().trim();
	}
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
100 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
5050

user output
5050

Test 2

Group: 1, 2, 3

Verdict:

input
100 2
5 5 2 4 3 5 3 4 3 2 3 4 5 4 4 ...

correct output
317

user output
310

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
100 10
71 60 61 96 25 10 10 9 84 85 1...

correct output
119

user output
119

Test 4

Group: 1, 2, 3

Verdict:

input
100 990000000
111122929 961821360 578238211 ...

correct output
4006

user output
3457

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
100 1000000000
553190572 453407680 667300705 ...

correct output
5050

user output
5050

Test 6

Group: 2, 3

Verdict: ACCEPTED

input
2000 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
2001000

user output
2001000

Test 7

Group: 2, 3

Verdict:

input
2000 2
4 4 1 4 2 3 1 2 1 3 5 2 2 4 4 ...

correct output
6340

user output
6274

Test 8

Group: 2, 3

Verdict:

input
2000 10
65 88 33 88 41 10 17 38 22 3 8...

correct output
2413

user output
2412

Test 9

Group: 2, 3

Verdict:

input
2000 999000000
746120950 772769620 721488968 ...

correct output
1287776

user output
1112341

Test 10

Group: 2, 3

Verdict: ACCEPTED

input
2000 1000000000
621947980 510355354 756705418 ...

correct output
2001000

user output
2001000

Test 11

Group: 3

Verdict:

input
100000 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
5000050000

user output
705082704

Test 12

Group: 3

Verdict:

input
100000 2
3 3 1 3 3 1 1 5 1 2 5 4 1 3 1 ...

correct output
317066

user output
313079

Test 13

Group: 3

Verdict:

input
100000 10
10 3 6 3 43 60 5 48 15 27 86 4...

correct output
123292

user output
123249

Test 14

Group: 3

Verdict:

input
100000 999990000
460235639 963048588 47270983 3...

correct output
4946886742

user output
648384965

Test 15

Group: 3

Verdict:

input
100000 1000000000
885457070 18257718 927615960 3...

correct output
5000050000

user output
705082704

Test 16

Group: 3

Verdict:

input
100000 50000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

correct output
3750075000

user output
-544892296

Test 17

Group: 3

Verdict:

input
100000 50000
100000 99999 99998 99997 99996...

correct output
3750075000

user output
-544892296