Alitaulukot

input/code.cpp: In function 'int main()':
input/code.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<xs.size(); i++)
                   ~^~~~~~~~~~
input/code.cpp:60:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = i + 1; j < xs.size(); j++)
                                 ~~^~~~~~~~~~~

// alijoukot.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <tuple>

using namespace std;

int main()
{
    string input1;
    string input2;
    getline(cin, input1);
    getline(cin, input2);

    int n = stoi(input1.substr(0, input1.find(" ")));
    input1.erase(0, input1.find(" ") + 1);
    int k = stoi(input1.substr(0, input1.find(" ")));

    vector<int> xs = vector<int>(n, 0);

    // from https://stackoverflow.com/questions/14265581/parse-split-a-string-in-c-using-string-delimiter-standard-c
    // converts the input string to integer vector
    size_t pos = 0;
    int i = 0;

    while ((pos = input2.find(" ")) != string::npos)
    {
        //xs.push_back(stoi(input2.substr(0, pos)));
        xs[i] = stoi(input2.substr(0, pos));
        // length of " " is 1
        input2.erase(0, pos + 1);
        i++;

    }
    xs[n - 1] = stoi(input2);

    map<int, tuple<int,int,int>> cache;
    int result = 0;

    for (int i=0; i<xs.size(); i++)
    {
        int s;
        auto cached = cache.find(i - 1);
        int m, M;
        if (cached != cache.end())
        {
            int v;
            tie(v, M, m) = cache[i - 1];
            s = v - 1;
        }
        else
        {
            m = xs[i];
            M = xs[i];
            s = 1;
            for (int j = i + 1; j < xs.size(); j++)
            {
                m = min(m, xs[j]);
                M = max(M, xs[j]);

                if ((M - m) > k) {
                    break;
                }
                else
                {
                    s++;
                }
            }
        }
        if ((xs[i] != m) & (xs[i] != M))
        {
            tuple<int, int, int> vals = {s,M,m};
            cache[i] = vals;
        }
        result += s;
    }
    std::cout << result << endl;
    
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 2, 3

Verdict: ACCEPTED

Test 8

Group: 2, 3

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 2, 3

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED