CSES - Datatähti 2021 alku

CSES - Datatähti 2021 alku - Results

Submission details
Task:	Alitaulukot
Sender:	nikolai2001
Submission time:	2020-10-05 19:38:38 +0300
Language:	C++ (C++17)
Status:	READY
Result:	37

Feedback
group	verdict	score
#1	ACCEPTED	11
#2	ACCEPTED	26
#3	WRONG ANSWER	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	1, 2, 3	details
#2	ACCEPTED	0.01 s	1, 2, 3	details
#3	ACCEPTED	0.01 s	1, 2, 3	details
#4	ACCEPTED	0.01 s	1, 2, 3	details
#5	ACCEPTED	0.01 s	1, 2, 3	details
#6	ACCEPTED	0.01 s	2, 3	details
#7	ACCEPTED	0.01 s	2, 3	details
#8	ACCEPTED	0.01 s	2, 3	details
#9	ACCEPTED	0.01 s	2, 3	details
#10	ACCEPTED	0.01 s	2, 3	details
#11	ACCEPTED	0.02 s	3	details
#12	ACCEPTED	0.02 s	3	details
#13	ACCEPTED	0.03 s	3	details
#14	ACCEPTED	0.05 s	3	details
#15	ACCEPTED	0.05 s	3	details
#16	WRONG ANSWER	0.06 s	3	details
#17	TIME LIMIT EXCEEDED	--	3	details

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 ...` view save

correct output
`5050` view save

user output
`5050` view save

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 ...` view save

correct output
`317` view save

user output
`317` view save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

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

correct output
`119` view save

user output
`119` view save

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 990000000 111122929 961821360 578238211 ...` view save

correct output
`4006` view save

user output
`4006` view save

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 1000000000 553190572 453407680 667300705 ...` view save

correct output
`5050` view save

user output
`5050` view save

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 ...` view save

correct output
`2001000` view save

user output
`2001000` view save

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 ...` view save

correct output
`6340` view save

user output
`6340` view save

Test 8

Group: 2, 3

Verdict: ACCEPTED

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

correct output
`2413` view save

user output
`2413` view save

Test 9

Group: 2, 3

Verdict: ACCEPTED

input
`2000 999000000 746120950 772769620 721488968 ...` view save

correct output
`1287776` view save

user output
`1287776` view save

Test 10

Group: 2, 3

Verdict: ACCEPTED

input
`2000 1000000000 621947980 510355354 756705418 ...` view save

correct output
`2001000` view save

user output
`2001000` view save

Test 11

Group: 3

Verdict: ACCEPTED

input
`100000 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`5000050000` view save

user output
`5000050000` view save

Test 12

Group: 3

Verdict: ACCEPTED

input
`100000 2 3 3 1 3 3 1 1 5 1 2 5 4 1 3 1 ...` view save

correct output
`317066` view save

user output
`317066` view save

Test 13

Group: 3

Verdict: ACCEPTED

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

correct output
`123292` view save

user output
`123292` view save

Test 14

Group: 3

Verdict: ACCEPTED

input
`100000 999990000 460235639 963048588 47270983 3...` view save

correct output
`4946886742` view save

user output
`4946886742` view save

Test 15

Group: 3

Verdict: ACCEPTED

input
`100000 1000000000 885457070 18257718 927615960 3...` view save

correct output
`5000050000` view save

user output
`5000050000` view save

Test 16

Group: 3

Verdict: WRONG ANSWER

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

correct output
`3750075000` view save

user output
`3750074415` view save

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 50000 100000 99999 99998 99997 99996...` view save

correct output
`3750075000` view save

user output
(empty)

Datatähti 2021 alku

Alitaulukot

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Tasks

Submissions (nikolai2001)