CSES - Datatähti 2021 alku - Results
Submission details
Task:Alitaulukot
Sender:Oxygenol
Submission time:2020-10-01 16:41:02 +0300
Language:C++ (C++17)
Status:READY
Result:37
Feedback
groupverdictscore
#1ACCEPTED11
#2ACCEPTED26
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.01 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details
#6ACCEPTED0.01 s2, 3details
#7ACCEPTED0.01 s2, 3details
#8ACCEPTED0.01 s2, 3details
#9ACCEPTED0.01 s2, 3details
#10ACCEPTED0.01 s2, 3details
#11ACCEPTED0.01 s3details
#12ACCEPTED0.02 s3details
#13ACCEPTED0.02 s3details
#14ACCEPTED0.03 s3details
#15ACCEPTED0.03 s3details
#16--3details
#17--3details

Code

#include <iostream>
#include <vector>
#include <ios>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
long long size;
std::cin >> size;
long long k;
std::cin >> k;
std::vector<long long> numbers = std::vector<long long>();
for (long long i = 0; i < size; i++) {
long long n;
std::cin >> n;
numbers.push_back(n);
}
long long count = size;
/*for (int i = 0; i < size; i++) {
int min = -1;
int max = -1;
for (int j = i; j < (int) numbers.size(); j++) {
int num = numbers[j];
if (num > max) {
max = num;
}
if (num < min || min == -1) {
min = num;
}
if ((max - min) > k) {
count += (j - i) * (j - i - 1) / 2;
int original = j;
int temp_max = -1;
int temp_min = -1;
while (true) {
j--;
int temp_num = numbers[j];
if (temp_max < temp_num) {
temp_max = temp_num;
}
if (temp_min > temp_num || temp_min == -1) {
temp_min = temp_num;
}
if ((temp_max - temp_min) > k || j <= 0) {
// std::cout << "Shifted by " << original - j << std::endl;
break;
}
}
// count -= (original - j + 1) * (original - j) / 2;
// std::cout << "j is " << i << std::endl;
i = j;
break;
} else if (j + 1 == size) {
count += (j - i + 1) * (j - i + 2) / 2;
i = size;
break;
}
}
std::cout << "Count is " << count << std::endl;
}*/
long long start = 0;
long long min = -1;
long long max = -1;
for (long long i = 0; i < size; i++) {
long long num = numbers[i];
if (num > max) {
max = num;
}
if (num < min || min == -1) {
min = num;
}
if (max - min > k) {
count += (i - start) * (i - start - 1) / 2;
// std::cout << "Incremented " << (i - start - 1) * (i - start) / 2 << std::endl;
long long original = i;
long long temp = numbers[i];
long long temp_max = temp;
long long temp_min = temp;
while (true) {
i--;
long long temp_num = numbers[i];
if (temp_max < temp_num) {
temp_max = temp_num;
}
if (temp_min > temp_num || temp_min == -1) {
temp_min = temp_num;
}
if (temp_max - temp_min > k) {
start = i + 1;
min = -1;
max = -1;
// std::cout << "Starting at " << start << std::endl;
// std::cout << "Original was " << original << " and we're at " << i << std::endl;
count -= (1 + (original - 1) - (i + 1)) * ((original - 1) - (i + 1)) / 2;
// std::cout << "Decremented " << (original - i + 1) * (original - i) / 2 << std::endl;
break;
}
}
} else if (i + 1 == size) {
// std::cout << "Nearing the end!" << std::endl;
count += (i - start) * (i - start + 1) / 2;
i = size;
break;
}
}
/*int count2 = 0;
for (int bar = 1; bar <= size; bar++) {
std::cout << bar << "/" << size << std::endl;
for (int i = 0; i < size - bar + 1; i++) {
bool valid = true;
int max = -1;
int min = -1;
for (int j = i; j < i + bar; j++) {
int num = numbers[j];
if (num > max) {
max = num;
}
if (num < min || min == -1) {
min = num;
}
if ((max - min) > k) {
valid = false;
break;
}
}
if (valid) {
count2++;
}
}
// std::cout << "Count was at " << count << " after bar " << bar << std::endl;
}
*/
std::cout << count << std::endl;
// std::cout << "Supposed to be: " << count2 << std::endl;
return 0;
}

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: ACCEPTED

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

correct output
317

user output
317

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: ACCEPTED

input
100 990000000
111122929 961821360 578238211 ...

correct output
4006

user output
4006

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: ACCEPTED

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

correct output
6340

user output
6340

Test 8

Group: 2, 3

Verdict: ACCEPTED

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

correct output
2413

user output
2413

Test 9

Group: 2, 3

Verdict: ACCEPTED

input
2000 999000000
746120950 772769620 721488968 ...

correct output
1287776

user output
1287776

Test 10

Group: 2, 3

Verdict: ACCEPTED

input
2000 1000000000
621947980 510355354 756705418 ...

correct output
2001000

user output
2001000

Test 11

Group: 3

Verdict: ACCEPTED

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

correct output
5000050000

user output
5000050000

Test 12

Group: 3

Verdict: ACCEPTED

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

correct output
317066

user output
317066

Test 13

Group: 3

Verdict: ACCEPTED

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

correct output
123292

user output
123292

Test 14

Group: 3

Verdict: ACCEPTED

input
100000 999990000
460235639 963048588 47270983 3...

correct output
4946886742

user output
4946886742

Test 15

Group: 3

Verdict: ACCEPTED

input
100000 1000000000
885457070 18257718 927615960 3...

correct output
5000050000

user output
5000050000

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
(empty)

Test 17

Group: 3

Verdict:

input
100000 50000
100000 99999 99998 99997 99996...

correct output
3750075000

user output
(empty)