CSES - Datatähti 2021 alku - Results
Submission details
Task:Alitaulukot
Sender:nikolai2001
Submission time:2020-10-05 19:39:20 +0300
Language: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.02 s3details
#12ACCEPTED0.02 s3details
#13ACCEPTED0.03 s3details
#14ACCEPTED0.05 s3details
#15ACCEPTED0.05 s3details
#160.06 s3details
#17--3details

Compiler report

input/code.cpp: In function 'int main(int, char**)':
input/code.cpp:156:42: warning: 'searchS' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 for(; searchE >= searchS && cV - numbers[searchE] <= diff; searchE--){
                       ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Code

#include <bits/stdc++.h>
#include <string>
#include <deque>
#include <algorithm>

using namespace std;

#define abs(x) (x < 0 ? -x : x)

#define CHUNCK 256
#define CSHIFT 8

struct Val{
    int val;
    int loc;

    friend  bool operator < (Val const &a, Val const &b){
        return a.val < b.val;
    }
};

struct Extreme{
    Val min;
    Val max;

    Extreme(){}

    Extreme(int val, int pos) : min({val, pos}), max({val, pos}){}

    inline int diff(){ return max.val - min.val; }
};

int main(int argv, char *argc[]){
    int len, diff;
    cin >> len >> diff;

    int *numbers = new int[len];
    // Chunck minimum/maximum values
    Extreme *chunkExtremes = new Extreme[(len >> CSHIFT) + 1]();

    for_each(numbers, numbers + len, [](auto &el){
        cin >> el;
    });

    long result = 0;

    static_assert(sizeof(long) == 8);

    int index = 0; // Current index

    int s = 0; // Start position of the sublist

    int cV; // Current value

    int extremeListIncrement;
    int exlI;
    int exlImin;
    
    Extreme sle; // The extremes of current sublist

    emptySList:
    s = index;
    sle = Extreme(numbers[index], index);

    extremeListIncrement = 0;
    exlImin = exlI = 0;
    chunkExtremes[exlI] = sle;

    while(++index < len){
        cV = numbers[index];

        if(cV <= sle.min.val){
            if(sle.min.val - cV > diff){
                // None of the current sub list fit...
                long n = index - s;
                result += (n*n + n) >> 1;
                goto emptySList;
            }
            sle.min = {cV, index};

            if(sle.diff() > diff){
                // Find the most rescent chunck in which the maximum does not fit.
                int i;
                int searchS = -1;
                Val mx = {0};

                for(i = exlI; i >= exlImin; i--){
                    if(chunkExtremes[i].max.val - cV > diff){
                        searchS = chunkExtremes[i].max.loc + 1;
                        break;
                    }else mx = max(mx, chunkExtremes[i].max);
                }
                exlImin = i;

                int chunckLast = index - extremeListIncrement - 2 - (exlI - i - 1) * CHUNCK;
                int searchE = min(index - 1,  chunckLast);

                chunkExtremes[i] = Extreme(numbers[searchE + 1], searchE + 1);

                assert(searchS != -1);

                // Look for values between searchS and searchE, and look for first
                // one that does not fit...
                for(; searchE >= searchS && numbers[searchE] - cV <= diff; searchE--){
                    if(numbers[searchE] < chunkExtremes[i].min.val){
                        chunkExtremes[i].min = {numbers[searchE], searchE};
                    }else if(numbers[searchE] > chunkExtremes[i].max.val){
                        chunkExtremes[i].max = {numbers[searchE], searchE};
                    }
                }

                if(searchE >= chunckLast) exlImin++;
                sle.max = max(chunkExtremes[exlImin].max, mx);

                // searchE now points to the last discarded value, therefore, values
                // between s and searchE discarded.

                // All numbers from s to n are to be discarded
                int n = searchE - s + 1;

                result += (long)(2*index - 2*s - n + 1) * n >> 1;

                s+= n;
            } 

        } else if(cV >= sle.max.val){
            if(cV - sle.max.val> diff){
                // None of the current sub list fit...
                long n = index - s;
                result += (n*n + n) >> 1;
                goto emptySList;
            }
            sle.max = {cV, index};

            if(sle.diff() > diff){
                // Find the most rescent chunck in which the minimum does not fit.
                int i;
                int searchS;
                Val mn = {2000000000};

                for(i = exlI; i >= exlImin; i--){
                    if(cV - chunkExtremes[i].min.val > diff){
                        searchS = chunkExtremes[i].min.loc + 1;
                        break;
                    }else mn = min(mn, chunkExtremes[i].min);
                }
                exlImin = i;

                int chunckLast = index - extremeListIncrement - 2 - (exlI - i - 1) * CHUNCK;
                int searchE = min(index - 1,  chunckLast);

                chunkExtremes[i] = Extreme(numbers[searchE + 1], searchE + 1);

                // Look for values between searchS and searchE, and look for first
                // one that does not fit...
                for(; searchE >= searchS && cV - numbers[searchE] <= diff; searchE--){
                    if(numbers[searchE] < chunkExtremes[i].min.val){
                        chunkExtremes[i].min = {numbers[searchE], searchE};
                    }else if(numbers[searchE] > chunkExtremes[i].max.val){
                        chunkExtremes[i].max = {numbers[searchE], searchE};
                    }
                }

                if(searchE >= chunckLast) exlImin++;
                sle.min = min(chunkExtremes[exlImin].min, mn);

                // searchE now points to the last discarded value, therefore, values
                // between s and searchE discarded.

                // All numbers from s to n are to be discarded
                int n = searchE - s + 1;

                result += (long)(2*index - 2*s - n + 1) * n >> 1;

                s+= n;
            } 

        }

        // Chunck management
        if(++extremeListIncrement >= CHUNCK){
            extremeListIncrement = 0;
            exlI++;
            chunkExtremes[exlI] = Extreme(index, cV);
        }else if(cV <= chunkExtremes[exlI].min.val){
            chunkExtremes[exlI].min = {cV, index};
        }else if(cV >= chunkExtremes[exlI].max.val){
            chunkExtremes[exlI].max = {cV, index};
        }
    }



    long n = index - s;
    result += (n*n + n) >> 1;

    cout << result << endl;

    return EXIT_SUCCESS;
}

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
3750074415

Test 17

Group: 3

Verdict:

input
100000 50000
100000 99999 99998 99997 99996...

correct output
3750075000

user output
(empty)