General Observations

Writing your own linked list implementation may not perform as well as the standard library version, compiler and library writers do their best to optimize their solutions.

The fact that the code allocates and deletes memory could be a speed issue that is costing additional time. The use of some other standard library feature such as a vector or array might perform much better. An array would be the fastest if you can use it. Using iterators rather than indexes could possibly improve the performance of each loop.

If you are worried about the time issue, it might be better to put the data directly into the proper data structures rather than repeatedly going over it multiple times, or least that seems to be what is going on with temp and v.

The code appears to ignore all the C++ best practices:

• The user of non-standard headers #include <bits/stdc++.h>.
• The use of using namespace std;.
• There are no functions or methods in the main program and it is 135 lines long with no vertical spacing between logic blocks.
• In the main program many of the variables have a single character as a name, this makes it more difficult to understand what the code is doing.
• If the code were self documenting (good variable names and good function names) there might not need to be comments, but right now the lack of comments are a problem.

As the code is written without functions, there is no automated way to find where the bottlenecks may be.

The code is not portable. The code is barely readable and therefore it can't be maintained.

Type Mismatch

The std::vector::size() function returns std::size_t, not int, this can cause issues. It is not likely in this case, but it could cause a performance issue if the wrong sized variable is used.

Review comment

Though not seeming to be too much, a 'pyramid' with (maximally) 1e6 "layers" would define the nature of each of the layers with 1e6 - 1 'M's and 'm's. There's no need to preload ALL those definitions (into ANOTHER 'slow-ish' LL).

Notice, a strong 'clue' has been given by the task designer. The value of any 'strength' is, maximally, the number of bricks in the bottom layer; maximally 1e6. All of those values used in the test appear on ONE line, and each could be as much as 7 digits wide. In a relatively extreme case, that second line of "values to use" could be as much as (6+1) * 1e6 = seven million digits and SPs long (the +1 for a SP character between each 'strength'). The next line is the "in flight" series of 'M' and 'm' layer definitions. This line, at maximally 1e6 characters FOLLOWS the longer line of "bottom layer strengths" (IE. multiple digits per strength of each brick versus one single character per layer.) The designer has given the clue that each 'M'/'m' can be read-in and utilised during processing, instead of as part of some preparation activity by the code.

Shift the cin so that the 'M'/'m' nature of the current supporting layer is retrieved only when needed for this layer's iteration. (Bottom layer has infinite support, of course.)

Recognise that (re-)instantiating vector<LinkedList> merged; (and any others) inside a loop does not come for 'free'. "Under the hood", those objects grow (or shrink) dynamically, too.

Analogy: 'stock' cars have their performance 'improved' by "expert" understanding of their operation 're-crafting' their subsystems for optimisation. Perhaps jettisoning the spare tire, and the rear seat will lighten the vehicle for better performance at Sunday's race meet-up. In other words, the 'convenience' and 'robustness' of using a standard library object risks introducing unseen and slightly costly, and in this case unnecessary, 'flexibility' that contributes to slowing down completion of the task.

A linked list is a wonderful "workhorse" data model; flexible, dynamic, and easy to code. However, they are, in use, likely to be "cache-unfriendly". Each useful item of "payload" data is welded to at least one 'pointer' value. This "bulking up" of each item reduces the density of useful data values. Result: more 'administrative' time spent fetching more lines into the cache. In this problem, each 4-byte int is accompanied by the OP's double linked list pointers; that is: 2x8 extra bytes required.

Additionally: the code's 'traversal while computing and storing' mimics pouring a liquid from one container to another. This could pour "back and forth" using fewer resources. Thus the code becomes more complicated by requiring a "parity awareness" the OP calls dir. Using two simple, contiguous arrays, one for reference values, the other for recording results, would be much simpler to understand and to code. Merely toggling between the two (reversing roles) requires only something like:

 // 'skeletal' demo int parity = 0; int arr[ 2 ] [ 1e6 ]; // fill array[0] with 'bottom layer' values ... // fetch this layer's strength: 'M' or 'm' int *src = &arr[ parity ][ 0 ]; parity = !parity; // 0 ==>> 1 and 1 ==>> 0 int *dst = &arr[ parity ][ 0 ]; ... ... // read "pairs" from *src // compute and assign to *dst // incr both ptrs and continue loop until done last brick on this layer // loop to begin computing next layer ... // have determined value of top brick 

NB: Shown as nested, each looping block should be in its own simple and easy-to-understand function. 'A' calls its worker 'B', 'B' calls its worker 'C'. Strive to keep things simple and modular...

NB: Consideration of "the program's stack" must not be overlooked. Massive arrays declared on the stack may risk triggering the dreaded "stack overflow".

After thought: Using a 'double linked list' may have been getting off to a bad start (unless that was part of the purpose to complete this challenge.)

An alternative would be to use the OP's LL, but as a "circular buffer" variation with 'single linked list' nodes. One traversal of an original ring of nodes, using a simple counter, could halt at the intended location (or its predecessor). A small bit of pointer manipulation could 'snip' the 'tail' node from the ring, and then the next traversal could begin. In practice, the dir of processing would not need to reverse. (Simpler.) The ultimate end would be detectable when the 'ring' has been pared-down to one node whose pointer points to itself. A variation on the insight noted by @jb_dk, would mean each single node and its adjacent node are combined to determine the new value of the current node, then the 'ribosome' moves on to make the next node its current node, and so on and so on. Use of C++ library container classes may be overkill for this function. Sometimes, the simplest solution can be the best solution, though.

Suggested improvement

Read about "Sobel Filters" used in image processing.

The parallel with your project is strong.

In brief, 2D "arrays" are used to store individual "pixel" values.
Traversing the array, the code uses "neighbouring" pixel values to 'tweak' value of each pixel, one-by-one.

Unchanging array size needs ONE allocation of working memory buffer.
Dynamic allocation can be relatively expensive.
Find and use an existing paradigm as 'model' for your objective.
In your case, it seems only two "levels" are needed.
(In your project, you may get away with two-or-three working buffers.
Depends on how you redesign the internal data representation.)

Familiarise yourself with "cache hits and misses".
Anything you can do that improves the possibility that using one parcel of data means the next parcel will already be available in the cache will increase performance.
E.g. if presented with 100K 'brick' problem and the data for 20 'bricks' fits in one line of cache, then increasing that "density" to 25 'bricks' per line of cache could achieve something approaching a 25% speed improvement. These are made-up values used only to illustrate the concept of designing toward "cache friendly" code (i.e. faster code).

Another analogue would be "Conway's Game of Life".

The first question to ask oneself is, "What exists that can I use as a good model for this task I'm undertaking?"

Perhaps, the next question is, "What is most important about this project?"
When used as they were intended to be used, the "generic" and reliable classes and functions offered by the language's libraries are suitable for most cases. When one wants/needs, for instance, "fast-fast", DIY code meticulously designed, coded and tested might be worth the time required for its development.

A better solution is to treat the problem as a pure math problem first and a programming task second.
So first look at the logic of the problem and derive a simpler algorithm that doesn't keep all the bricks of all the layers in memory at the same time.
Next implement the optimized algorithm to complete in 4 seconds.

Somehow, you will need to load the input in less than 4 seconds and find the result in the leftover time.

Given the structure of the input data, perhaps use the bits from the m/M row to determine if the final result will be min of all bottom bricks (BBs), max of all BBs or something else.
Then apply that conclusion to the loop over the numbers row. This should reduce the memory need to much less .

Example resoning: If the 1 brick layer is m, only the min of the 2 brick layer, if it is M, only the max of the 2 brick layer.
If the 2 brick layer is the same, the conclusion applies also to the 3 brick layer.
If the tip is m and the 2 BL is M, then the formula is min(max(a, b), max(b, c)) = max(b, min(a, c)).
If the opposite min(b, max(a, c)).
Iterate the argument all the way to the bottom layer and input the strengths as needed to create an algorithm.

A pure programming approach would be to create a streaming but direct algorithm. Load the m/M bits into a compact bit array (N bits) and keep an array of last brick strengths per layer (N values).
As each strength number is loaded, update the array.
At the end the final value in the entry for the tip will be the result.

An even simpler programming approach would be to have an array of the strengths in the current layer (initially the input values), and then apply the layer type overwriting all but he last array element, which is logically discarded, but not deallocated.
In the end the array will contain one valid brick strength (the result) and N-1 values describing each brick on the ending slope of the pyramid.

To understand this kind of thinking read the first few chapters of "The Art of Computer Programming" by Donald Knuth and do a few of the exercises.

Overall, these suggestions should reduce the problem from O(N^2) to O(N) in memory and perhaps calculation time (my last 2 suggestions still require about N*N/2 min or max operations).
In contrast your code would seem to allocate a lot of extra space for the strength of all approximately N*N/2 bricks. For N=1e6, that is 5e11 ints of memory plus all your unneeded pointers.

Your mistakes are not uncommon.
In particular, some versions of Microsoft Windows used code like yours to decide which updates to install and in what order, causing the update management processes to run for a very long time on every windows computer in the world every month.