A team of engineers is planning the construction of a new factory. For their factory to be reliable, they want to create various items at a constant and reliable rate of units per second. They can use different crafting stations to craft these materials. Each crafting station has its own speed, affecting a crafting process. Each material has its own crafting recipe that has to be executed in a specific crafting station.
You are given the description of every crafting station together with the recipes for every material and intermediate material that you need. You are also given a list of materials that you have to produce at a certain rate so that your factory is reliable.
We consider a configuration of machines to be optimal if by removing any of the machines from the configuration, there is at least a material such that its production rate is smaller than the required amount.
The first line of input will contain an integer $$$M$$$ ($$$1 \leq M \leq 100$$$) representing the number of types of machines we have. On each of the following $$$M$$$ lines there will be a string $$$n$$$, or ($$$1 \leq |n| \leq 30$$$) and a number $$$s$$$ ($$$0.01 \leq s \leq 100$$$) representing the name and the speed-rate of one machine.
The following line of input will contain an integer $$$N$$$ ($$$1 \leq N \leq 100$$$) representing the number of recipes.
Following $$$N$$$, there will be the description of each recipe. On the first line of a recipe, there is the string $$$p$$$ ($$$1 \leq |p| \leq 30$$$) representing the name of the material to be crafted, another string $$$l$$$ ($$$1 \leq |l| \leq 30$$$) representing the name of the crafting station used during the process and a number $$$t$$$ ($$$0.01 \leq t \leq 100$$$), representing the time needed to craft the material on normal speed in seconds. On the following line, there is a number $$$k$$$ ($$$0 \leq k \leq 15$$$) representing the number of materials needed during production.
Each of the following $$$k$$$ lines will contain a string $$$n$$$ ($$$1 \leq |n| \leq 30$$$) representing the name of a required material and an integer $$$c$$$ ($$$1 \leq c \leq 10$$$) representing the number of units of the corresponding material required in the process.
Suppose that a recipe takes $$$t$$$ seconds to craft in normal speed. That is, given a machine with speed $$$1$$$ and the required materials, it would take $$$t$$$ seconds to craft the recipe. On the other hand, if the speed is $$$0.5$$$, the machine would be two times slower than normal, therefore after feeding it the required materials, it would take twice as long to craft. That is, the recipe would be executed in $$$2 \times t$$$ seconds.
Each recipe requires exactly one machine of type $$$l$$$. After a recipe is executed, we will obtain exactly one material $$$p$$$.
The next line will contain an integer $$$Q$$$ ($$$1 \leq Q \leq 100$$$) representing the number of required materials to be produced.
Each of the following $$$Q$$$ lines will contain a string $$$m$$$ ($$$1 \leq |m| \leq 30$$$) representing the name of a required material to be produced, and an integer $$$c$$$ ($$$1 \leq c \leq 10$$$) representing the number of units of that material required to be produced per second.
The numbers $$$s$$$ and $$$t$$$ are given as floating points with exactly two decimal places.
It is guaranteed that there exists a valid configuration.
It is guaranteed that the rate of production for every material in the optimal solution does not exceed $$$10^9$$$ units per second.
Each material can be crafted using a unique recipe.
It is guaranteed that there are no cyclic dependencies. That is, there is no sequence of recipes $$$r_1, r_2,\dots, r_k$$$ such that $$$\forall i\ s.t.\ 1 \leq i \lt k$$$ the recipe $$$r_i$$$ requires you to craft recipe $$$r_{i+1}$$$, and recipe $$$r_k$$$ requires you to craft recipe $$$r_1$$$.
It is guaranteed that any string read contains only lower-case letters from the English alphabet and underscores (character '_').
The output should contain $$$N$$$ lines. On the $$$i$$$-th line you have to output $$$p_i$$$ $$$l_i$$$ $$$r_i$$$ where $$$r_i$$$ represents the number of machines required to execute the $$$i$$$-th recipe.
3 assembler 0.50 furnace 0.50 mining_well 0.55 6 iron_plate furnace 3.20 1 iron_ore 1 copper_plate furnace 3.20 1 copper_ore 1 iron_ore mining_well 1.00 0 copper_ore mining_well 1.00 0 copper_cable assembler 0.50 1 copper_plate 1 electronic_circuit assembler 0.50 2 iron_plate 1 copper_cable 3 1 electronic_circuit 10
iron_plate furnace 64 copper_plate furnace 192 iron_ore mining_well 19 copper_ore mining_well 55 copper_cable assembler 30 electronic_circuit assembler 10
3 assembler 0.50 furnace 0.50 mining_well 0.55 4 iron_plate furnace 3.20 1 iron_ore 1 iron_ore mining_well 1.00 0 iron_gear assembler 0.50 1 iron_plate 2 transport_belt assembler 0.50 2 iron_plate 1 iron_gear 1 1 transport_belt 7
iron_plate furnace 135 iron_ore mining_well 39 iron_gear assembler 7 transport_belt assembler 7
In the first example, because the assembler has a speed of 0.50 and the recipe for crafting an electronic circuit takes 0.50 seconds to craft an item, we will craft one electronic circuit per second for each assembler we have. Because we need to have a rate of production of 10 units per second, we will require 10 assemblers.
Each assembler used for the production of electronic circuits requires one iron plate, so we need a production rate of $$$10$$$ iron plates per second. We can use the first recipe to craft iron plates, which take $$$3.2 / 0.5 = 6.4$$$ seconds to craft each, so we need $$$64$$$ furnaces for iron plates. Each furnace needs an iron ore to complete the task so we will require $$$10$$$ iron ores per second to sustain the process. Using the third recipe, we will require $$$19$$$ mining wells to craft $$$0.55 \times 19 = 10.45$$$ iron ores per second. If we used only 18 mining wells for this recipe, we would have only crafted $$$0.55 \times 18 = 9.9$$$ iron ores per second, which is less then the rate of $$$10$$$ iron ores per second required.
This problem is similar to YsaeSort. Please read the problem statement carefully to understand the differences
You are given an array of $$$N$$$ non-negative integers and a list of $$$Q$$$ operations that need to be performed on it. Each operation has the following meaning:
- $$$l$$$ $$$r$$$ $$$(1 \leq l \leq r \leq N)$$$ - find the minimum required cost to sort the contiguous subsequence $$$[l, r]$$$ of the array
The cost required to sort a substring, $$$[l, r]$$$ ($$$1 \leq l \leq r \leq N$$$), is defined as follows. You are only allowed to swap consecutive elements from the substring (any pair of indices $$$(i, i + 1)$$$ such that $$$l \leq i \leq r - 1$$$). The cost of swapping two consecutive elements is the product of the elements being swapped. The cost of sorting the entire substring is defined as the maximum cost among each individual swap.
Please note that the operations won't alter the structure of the array.
The first line of input will contain one integer $$$N$$$ ($$$1\leq N \leq 2 \cdot 10^5$$$), representing the number of elements of the array.
The second line of input will contain $$$N$$$ integers ($$$0 \leq A[i] \leq 10^9$$$, $$$1\leq i \leq N$$$), the elements of the array.
The third line of input will contain one integer $$$Q$$$ ($$$1\leq Q \leq 2 \cdot 10^5$$$), representing the number of operations.
Each of the following $$$Q$$$ lines will contain one operation as described in the problem statement.
For every query output the required cost to sort the substring.
10 10 9 8 7 6 5 4 3 2 1 8 1 2 1 3 1 10 9 10 1 4 3 4 2 3 1 4
90 90 90 2 90 56 72 90
Recently, you have inherited a field from your great-great-grandfather, The Great Farmer. The field can be viewed as a rectangular matrix, with $$$n$$$ rows and $$$m$$$ columns. You want to continue the legacy of your great-great-grandfather, and start cultivating the field with two types of plants: wheat and sunflower.
You soon realize you can turn this into a business: in each cell of the field, you can put one of the two seeds. Planting wheat at cell $$$(i, j)$$$ earns you $$$A[i][j]$$$ euros, while planting sunflower at the same cell $$$(i, j)$$$ earns you $$$B[i][j]$$$ euros.
Unfortunately, you soon observe that if you plant different types of plants in adjacent cells, their roots will tangle up and it will cost you an amount of money to fix.
You are now eager to find what is the maximum amount of money you can receive if you optimally plant exactly one of the two seeds in each cell.
The first line of the input will contain two integers $$$N$$$ ($$$1 \leq N \leq 70$$$) and $$$M$$$ ($$$1\leq M \leq 70$$$), representing the number of rows and columns of the field.
The next $$$N$$$ lines will contain $$$M$$$ integers ($$$1 \leq A[i][j] \leq 10^5$$$), denoting the reward of planting wheat in cell $$$(i, j)$$$.
The next $$$N$$$ lines will contain $$$M$$$ integers ($$$1 \leq B[i][j] \leq 10^5$$$), denoting the reward of planting sunflower in cell $$$(i, j)$$$.
The next $$$N$$$ lines will contain $$$M - 1$$$ integers ($$$1 \leq C_1[i][j] \leq 10^5$$$), denoting the penalty of planting different seeds in cells $$$(i, j)$$$ and $$$(i, j + 1)$$$.
The next $$$N - 1$$$ lines will contain $$$M$$$ integers ($$$1 \leq C_2[i][j] \leq 10^5$$$), denoting the penalty of planting different seeds in cells $$$(i, j)$$$ and $$$(i + 1, j)$$$.
The output file will contain a single number, the maximum amount of money you can earn.
2 2 1 6 7 1 5 1 1 3 1 1 2 1
16
Having been an amazing skateboarder, you know how cool flips are: Heelflips, Kickflips, Frontflips and so on. You know what it's all about!
Because you retired, today you are going to have fun with a different type of flip.
You are given an array $$$a$$$ of $$$N$$$ numbers represented on $$$K$$$ bits and a number $$$P$$$.
Exactly $$$P$$$ times you have to pick a bit from a number and flip it (you are allowed to flip the same bit as many times as you want) such that after you perform all the flips, the following sum is maximized:
where $$$\oplus$$$ represents the bit-wise xor operator.
In case there are multiple such solutions, you should print any.
The first line contains integers $$$N$$$, $$$K$$$ and $$$P$$$. It is guaranteed that $$$1 \leq N \leq 10^5$$$, $$$1 \leq K \leq 30$$$ and $$$1 \leq P \leq N*K$$$.
The next line contains $$$N$$$ integers, the array $$$a$$$. It is guaranteed that $$$0 \leq a_i \lt 2^K$$$ for all $$$1 \leq i \leq N$$$.
The output file should contain exactly $$$P$$$ lines each containing two integers $$$i$$$ and $$$j$$$ such that $$$1 \leq i \leq N$$$ and $$$0 \leq j \lt K$$$, which represent flipping bit $$$j$$$ of number $$$a_i$$$. Namely, $$$a_i \Leftarrow a_i \oplus 2^j$$$.
You are allowed to flip the same bit multiple times. Any solution that maximizes the sum is valid. The order in which you output the operations is not important.
2 5 1 0 31
1 0
4 2 2 0 0 2 2
4 0 3 0
5 6 4 63 15 0 10 5
5 5 4 5 4 4 5 4
Charlie and Dan play a game on $$$N$$$ piles numbered from $$$1$$$ to $$$N$$$ from left to right. Each pile contains a strictly positive number of stones.
The rules are simple:
- The players take turns. Charlie is first.
- Both players play optimally.
- At a turn, a player takes a strictly positive number of stones from the leftmost non-empty pile and moves them to the neighbouring right pile.
- A player will lose if, at the player's turn, the only non-empty pile is pile number $$$N$$$.
Who wins the game?
The first line of input will contain an integer $$$N$$$ ($$$2\leq N \leq 10^3$$$), the number of piles.
The next line contains $$$N$$$ integers $$$v_1, v_2, ... , v_n$$$ ($$$1\leq v_i \leq 10^9$$$).
The output should contain the name of the winner of the game: "Charlie" or "Dan".
3 2 2 2
Charlie
Mike just got an internship at the local internet service provider, DNS. Knowing that Mike is familiar with IPs, they have asked him to implement a management system for their clients supporting a few operations. Some of those operations are client specific, while others are DNS (company) specific. Mike doesn't actually know much about IPs, so he has asked for your help.
IPs range from 0 to $$$10^9$$$ and are all initially available to all clients. There are $$$N$$$ countries (numbered from $$$0$$$ to $$$N - 1$$$), each with its own set of IPs modeled as a union of intervals. There are $$$M$$$ clients (numbered from $$$0$$$ to $$$M - 1$$$) Mike needs to help out with and $$$Q$$$ queries to answer. The queries have the following form:
- Blacklist a country for all clients. Blacklisting a country blocks all the IPs corresponding to that country and the countries it is merged with.
- Blacklist an interval of IPs [$$$X$$$, $$$Y$$$] for all clients.
- Blacklist a country for a specific client. Similar to query $$$1$$$, but the impact is limited to one client.
- Blacklist an interval of IPs [$$$X$$$, $$$Y$$$] for a specific client.
- Whitelist a country for a specific client. Whitelisting a country whitelists all the IPs corresponding to that country and the countries it is merged with. Note that a whitelist takes precedence ahead of any previous or future applicable blacklist for this client.
- Whitelist an interval of IPs [$$$X$$$, $$$Y$$$] for a specific client. Note that a whitelist takes precedence ahead of any previous or future applicable blacklist for this client.
- Countries $$$X$$$ and $$$Y$$$ are merged together. Note that the merge behavior will only be reflected in new queries. If the countries had previous merges, the whole group of countries will be merged.
- How many IPs does a client have access to within an interval [$$$X$$$, $$$Y$$$]?
Since the input and output are quite large, we recommend using fast methods of reading and writing, such as desynchronization in C++.
The first line contains integers $$$N$$$, $$$M$$$, $$$Q$$$. It is guaranteed that $$$1 \leq N \leq 10^4$$$, $$$1 \leq M \leq 10$$$, $$$1 \leq Q \leq 10^5$$$.
On the next $$$N$$$ lines, each line contains an integer $$$N_i$$$ followed by $$$2 \times N_i$$$ integers ($$$X_i^1, Y_i^1, ..., X_i^{N_i}, Y_i^{N_i}$$$) corresponding to $$$N_i$$$ intervals. Each integer is between $$$0$$$ and $$$10^9$$$. The union of these $$$N_i$$$ intervals represents the country's set of IPs. Note that $$$\sum_{i=1}^{N} N_i \leq 10^5$$$.
The next $$$Q$$$ lines describe the queries. Each of them starts with an integer $$$1 \leq type \leq 8$$$ representing the query type followed by a number of integers depending on the query type:
- $$$countryIdx$$$, where $$$0 \leq countryIdx \lt N$$$.
- $$$X$$$, $$$Y$$$ where $$$0 \leq X \leq Y \leq 10^9$$$.
- $$$clientIdx$$$, $$$countryIdx$$$, where $$$0 \leq clientIdx \lt M$$$, $$$0 \leq countryIdx \lt N$$$.
- $$$clientIdx$$$, $$$X$$$, $$$Y$$$, where $$$0 \leq clientIdx \lt M$$$, $$$0 \leq X \leq Y \leq 10^9$$$.
- $$$clientIdx$$$, $$$countryIdx$$$, where $$$0 \leq clientIdx \lt M$$$, $$$0 \leq countryIdx \lt N$$$.
- $$$clientIdx$$$, $$$X$$$, $$$Y$$$, where $$$0 \leq clientIdx \lt M$$$, $$$0 \leq X \leq Y \leq 10^9$$$.
- $$$country1Idx$$$, $$$country2Idx$$$, where $$$0 \leq country1Idx \lt N$$$, $$$0 \leq country2Idx \lt N$$$.
- $$$clientIdx$$$, $$$X$$$, $$$Y$$$, where $$$0 \leq clientIdx \lt M$$$, $$$0 \leq X \leq Y \leq 10^9$$$.
The output file should contain a line per query type $$$8$$$ representing the total number of visible IPs within that interval for that client.
2 1 12 1 1 100 1 500 1000 8 0 1 1000 1 0 2 800 900 8 0 1 1000 7 0 1 3 0 0 8 0 1 1000 4 0 200 400 8 0 1 1000 5 0 1 6 0 95 499 8 0 1 1000
1000 799 399 198 1000
Once upon a time, there was a game show host named Monty Hall. He loved nothing more than to watch his contestants squirm as they tried to win fabulous prizes. One day he decided to spice things up by introducing a new game.
Eager to win a big prize and live a stress free life, Gigel decided to bite the bullet and take Monty Hall on his challenge.
The challenge is simple, Monty would show the contestant $$$N (1 \leq N \leq 10^5)$$$ doors, the contestant is initially positioned in front of the first door, however he can only unlock a door once he has moved onto that particular door. Gigel now has a selection of $$$N$$$ operations of the following types: he can select a number $$$i (1 \leq i \leq N)$$$ and must move $$$i$$$ doors to the right. The cost of this operation is equal to $$$C_i(1 \leq C_i \leq 10^5)$$$. It's important to note that these doors are arranged in a circle, hence the door to the right of the $$$N^{th}$$$ door is door number one.
Moreover, because Monty does not want to make it easy for Gigel to go from one door to the next one, the costs that he set for these operations are non-increasing. Formally, $$$C_i\geq C_{i+1}$$$ for all $$$1\leq i \leq N-1$$$.
In order to win Gigel has to open every door while keeping the overall cost as low as possible.
Gigel didn't exactly ace his Math classes in his younger days. Let's just say he was more interested in playing hooky and catching up on his beauty sleep. Now, he's hoping to make up for lost time and is seeking your help to crack this door-opening puzzle. And don't worry, he's willing to share the spoils of victory with you. After all, what are friends for, right?
The first line of input contains one integer, $$$N (1 \leq N \leq 10^5)$$$, the number of doors.
The second line of input contains $$$N$$$ integers, where the $$$i^{th}$$$ element represents the cost of operation $$$i$$$ with $$$1 \leq C_i \leq 10^5$$$. It is guaranteed that $$$C_i\geq C_{i+1}$$$ for all $$$1\leq i \leq N-1$$$.
The output file should contain one integer representing the minimum cost to open all $$$N$$$ doors.
5 4 3 3 3 3
15
Starting from door one, you take a 2-step move to the right at a cost of 3 and open door 3. Next, you make another 2-step move to the right with a cost of 3, opening door 5. Subsequently, you take a 4-step move to the right with a cost of 3, opening door 4. Afterward, you move 3 steps to the right at a cost of 3, opening door 2. Finally, you move 4 steps to the right with a cost of 3, opening door 1. In total, the cost incurred is 3+3+3+3+3, which amounts to 15.
Iuli has just been employed to be a border policeman at the Nădlac checkpoint (at the border between Romania and Hungary). His job is to verify the papers of all the trucks that pass the border. Each truck is assigned an unique color which can be either red, orange, yellow, green, blue, indigo or violet (the rainbow colors). The color of the truck is an important marker that helps the border police estimate the priority of each transport, more precisely:
One day, the paper checking system (used by Iuli to check a truck driver's papers) broke down. Because the system is down, no truck is crossing the border until it is repaired. Due to the situation, Iuli's boss is overwhelmed with requests. Iuli knows that his boss doesn't pay him for nothing, so he expects that the boss will assign him some of his tasks.
There are three types of events that can occur while the system is broken:
Type 1) A group of one or more trucks will arrive at the back of the queue.
Type 2) The boss will give Iuli a paper with the colors of a sequence of trucks that is standing in the queue and asks Iuli to check their papers. The problem is that Iuli's boss is, as we said above, overwhelmed by the situation, so he might give Iuli a sequence that might not even exist in the truck queue. If the sequence exists, Iuli will simply check their papers. If the sequence does not exist, Iuli does not know what to do. He can't go ask the boss because he is too busy with managing the crisis. Iuli decides that in case the sequence provided does not exist, he will simply choose the most important sequence of trucks that he can find in the queue, that is less important than the provided sequence.
We say that a sequence $$$X$$$ of trucks is more important than a sequence $$$Y$$$ if one of the following conditions apply:
- There exists $$$Z$$$ another valid sequence of trucks such that $$$X = Y + Z$$$ (where $$$+$$$ is string concatenation)
- There exists $$$k$$$ an index such that $$$X_i = Y_i$$$ for every $$$i \lt k$$$ and $$$X_k \gt Y_k$$$. (where $$$X_i$$$ represents the $$$i$$$-th truck from the X sequence of trucks).
Type 3) The boss comes with a question that came from the ministry of transportation of Romania to check on the situation. Because he is again overwhelmed by the situation, he passes the question to Iuli to write a response. Fortunately, the ministry will always ask the same question: the sum of lengths of all distinct sequences. The ministry is not interested in all the trucks in the sequence, so they want the sum of the sequences that contain only colors from a list provided by them.
Iuli is worried of what is to come, so he wants you to help him prepare by resolving a scenario containing events as described above.
You will receive the events that will occur (in the order they are given) in a scenario. For each event of Type 2 you have to find the sequence of trucks that Iuli will choose to verify their papers. For each event of Type 3 you have to find the answer to ministry's question.
At the beginning of each scenario, at the border there are no trucks waiting to pass.
The first line of input will contain one integer $$$Q$$$ ($$$1\leq Q \leq 500$$$) representing the number of events that are occurring in our scenario.
The next $$$Q$$$ lines will each contain an event:
- $$$1$$$ $$$S$$$, meaning that a sequence of trucks $$$S$$$ ($$$1\leq |S| \leq 10^5$$$) codified by their colors. It is guaranteed that $$$\sum_{}^{} |S| \leq 10^5$$$.
- $$$2 $$$ $$$T$$$, meaning that the boss wants to check the papers of sequence $$$T$$$ ($$$1\leq |T| \leq 10^5$$$).
- $$$3 $$$ $$$C$$$, meaning that the ministry wants the answer for the color-sequence $$$C$$$ ($$$1\leq |C| \leq 7$$$).
The truck sequences received in input and required in the output will be codified by their color.
A sequence $$$x_1$$$, $$$x_2$$$, ... $$$x_N$$$ is the codification by color of a sequence of $$$N$$$ trucks where:
- If $$$x_i = R$$$ means that the $$$i$$$-th truck in the sequence is red.
- If $$$x_i = O$$$ means that the $$$i$$$-th truck in the sequence is orange.
- If $$$x_i = Y$$$ means that the $$$i$$$-th truck in the sequence is yellow.
- If $$$x_i = G$$$ means that the $$$i$$$-th truck in the sequence is green.
- If $$$x_i = B$$$ means that the $$$i$$$-th truck in the sequence is blue.
- If $$$x_i = I$$$ means that the $$$i$$$-th truck in the sequence is indigo.
- If $$$x_i = V$$$ means that the $$$i$$$-th truck in the sequence is violet.
The trucks in a sequence are ordered from the closest truck to the border checkpoint to the furthest away.
For the type 3 event you will receive a sequence of non-empty, non-repeating colors codifying the list of colors provided by the ministry.
The output shall contain the answer to queries of type 2 and 3.
6 1 GBIOOYBIOOYBB 2 R 3 O 1 OOO 2 R 3 O
OOYBB 3 OOO 6
"O" and "OO" are the only sequences with letters "O", thus the resulting total length is 3 for the first query of type 3.
"O", "OO" and "OOO" are the only sequences with letters "O", thus the resulting total length is 6 for the second query of type 6.
Palindromes are very interesting! However, asking you to simply print whether a string is a palindrome or not would make life too easy.
Let us, then, define how to calculate the degree of a palindrome. There are three possible cases, as follows:
- For a given string $$$s$$$, if $$$s$$$ is not a palindrome, then its degree will be $$$0$$$.
- For a given string $$$s$$$, if $$$s$$$ has length one, then its degree will be $$$1$$$.
- For a given string $$$s$$$, if $$$s$$$ is a palindrome of a length greater than one, then its degree will be the degree of its left half (middle character included in case the length of $$$s$$$ is an odd number) plus one.
For instance, string $$$abc$$$ has degree $$$0$$$ since it is not a palindrome, string $$$a$$$ is a palindrome of degree 1 since it contains only one character, and $$$ababa$$$ is a palindrome of degree 2 since $$$aba$$$ is a palindrome of degree 1.
You are given a string $$$s (1 \leq |s| \leq 10^5)$$$ and an integer $$$k$$$. For every $$$i = \overline{1, k}$$$, you should answer how many substrings of $$$s$$$ have degree $$$i$$$. Please note that a substring is formed of characters that are on consecutive positions in $$$s$$$.
The first line of input will contain string $$$N (1 \leq N \leq 10^5)$$$, the length of the string, and $$$K (1 \leq K \leq 30)$$$, the maximum degree that you should compute the answer for.
The second line of input will contain the string $$$s$$$, containing only lowercase letters of the Latin alphabet.
The output should be formed of one line, containing the answers for the $$$K$$$ degrees, starting with the answer for degree $$$1$$$ and ending with the answer for the $$$K^{th}$$$ degree, separated by spaces.
4 3 bbab
5 1 0
3 3 bbb
3 2 1
Alice and Bob play a game on $$$N$$$ squares numbered from $$$1$$$ to $$$N$$$ from left to right. The squares can either be empty or have a pawn. Initially, there are $$$M$$$ pawns, each having a position and a color. Two pawns cannot have the same position at any given time.
The game is played by taking turns and Alice is the first one to move. A player's turn consists of choosing a pawn with at least one empty square to the left. The player can move this pawn to the left any strictly positive number of squares, but it cannot move over or to the position of another pawn. Also, a pawn cannot go over square $$$1$$$, since square $$$1$$$ has no other squares to the left.
After a pawn of color $$$C$$$ is moved by $$$X$$$ squares to the left, all the pawns to the right of the moved pawn until the next pawn of color $$$C$$$ (or all the pawns to the right if there are no more pawns of color $$$C$$$) will move $$$X$$$ squares to the left as well.
A player will lose if there are no more valid moves at the turn (there are no pawns with at least one empty square to the left). It is assumed that both players play optimally.
Let's provide an example of a player turn. We have the following configuration of $$$17$$$ squares where a number represents a pawn of that color:
| $$$ \ $$$ | $$$ \ $$$ | $$$2$$$ | $$$ \ $$$ | $$$3$$$ | $$$ \ $$$ | $$$1$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$2$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$3$$$ | $$$ \ $$$ | $$$2$$$ | $$$ \ $$$ | $$$1$$$ |
If the pawn at square $$$3$$$ is moved by $$$1$$$ square, it will result in the following configuration:
| $$$ \ $$$ | $$$2$$$ | $$$ \ $$$ | $$$3$$$ | $$$ \ $$$ | $$$1$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$2$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$3$$$ | $$$ \ $$$ | $$$2$$$ | $$$ \ $$$ | $$$1$$$ |
You are given $$$Q$$$ queries of two types:
- Add a pawn to the position $$$pos$$$ of color $$$col$$$.
- Remove a pawn from position $$$pos$$$.
After each query, you should print the name of the player that will win with the newly created configuration.
The first line of input will contain two integers $$$N$$$ ($$$1\leq N \leq 10^9$$$), $$$M$$$ ($$$1\leq M \leq 10^5$$$) representing the number of squares and pawns.
The next $$$M$$$ lines will each contain a pair of integers $$$pos$$$ ($$$1\leq pos \leq N$$$) and $$$col$$$ ($$$1\leq col \leq 5$$$) which means that there is a pawn of color $$$col$$$ at position $$$pos$$$.
The next line will contain $$$Q$$$ ($$$1\leq Q \leq 10^5$$$), the number of queries
The next $$$Q$$$ lines will each contain a query:
- $$$1 $$$ $$$pos $$$ $$$col$$$, meaning that a pawn of color $$$col$$$ is added at position $$$pos$$$. It is guaranteed that there are no pawns at position $$$pos$$$. ($$$1\leq pos \leq N$$$, $$$1\leq col \leq 5$$$)
- $$$2 $$$ $$$pos$$$, meaning that the pawn at position $$$pos$$$ is removed. It is guaranteed that there is a pawn at position $$$pos$$$. ($$$1\leq pos \leq N$$$)
The output should contain $$$Q$$$ lines. On line $$$i$$$, print out the answer corresponding to query $$$i$$$.
30 6 3 1 6 2 11 3 14 2 17 3 27 1 4 1 24 1 2 24 1 23 1 1 29 2
Bob Alice Alice Bob
Initial configuration:
| $$$ \ $$$ | $$$ \ $$$ | $$$1$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$2$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$3$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$2$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$3$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$1$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ |
After query $$$1$$$:
| $$$ \ $$$ | $$$ \ $$$ | $$$1$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$2$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$3$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$2$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$3$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$1$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$1$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ |
After query $$$2$$$:
| $$$ \ $$$ | $$$ \ $$$ | $$$1$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$2$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$3$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$2$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$3$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$1$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ |
After query $$$3$$$:
| $$$ \ $$$ | $$$ \ $$$ | $$$1$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$2$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$3$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$2$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$3$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$1$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$1$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ |
After query $$$4$$$:
| $$$ \ $$$ | $$$ \ $$$ | $$$1$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$2$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$3$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$2$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$3$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$1$$$ | $$$ \ $$$ | $$$ \ $$$ | $$$ \ $$$ | $$$1$$$ | $$$ \ $$$ | $$$2$$$ | $$$ \ $$$ |
Help!
On your way to the AGM(Annual Galley Meeting) you are under attack by pirates trying to destroy your ship.
The way these pirates operate is quite different from what you would usually expect: they do not shoot at you with cannons, but rather bomb entire regions of the ocean. Furthermore, the captain of the ship does not use the usual Arrr!, but rather yells Yeey! or Ooh! whenever a ship is successfully hit or not. Truly bizzare.
Luckily for you, the pirates always operate the same way, so you already know the regions that will be bombed before the trip. This way you can plan how big of a ship to embark on and what route to pick!
The region you will be passing through is a rectangular grid with $$$N$$$ rows and $$$M$$$ columns.
You know that there are $$$B$$$ axis-aligned rectangular areas inside this grid that have been bombed.
Your ship can be thought of as a sequence of consecutive cells in the same line or column of the grid.
For $$$S$$$ placements of the ship, you would like to know the state of the ship after the bombing. The state can be one of the following:
- MISS, if none of the cells of the ship was hit by a bomb.
- HIT, if at least one of the cells of the ship was hit by at least a bomb.
- SUNK, if every cell of the ship was hit by at least a bomb.
The first line contains integers $$$N$$$ and $$$M$$$, the dimensions of the grid. It is guaranteed that $$$1 \leq N, M \leq 10^5$$$.
The next line contains integer $$$B$$$, the number of bombs. It is guaranteed that $$$1 \leq B \leq 2*10^5$$$.
The next $$$B$$$ lines each contain integers $$$x1$$$, $$$y1$$$, $$$x2$$$, $$$y2$$$ describing a bombed rectangular area between cells $$$(x1, y1)$$$ and $$$(x2, y2)$$$. It is guaranteed that $$$1 \leq x_1 \leq x_2 \leq N$$$ and $$$1 \leq y_1 \leq y_2 \leq M$$$. The bombs can overlap.
The next line contains integer $$$S$$$, the number of ships whose status we would like to know. It is guaranteed that $$$1 \leq S \leq 2*10^5$$$.
Each of the next $$$S$$$ lines contains a description of a ship:
- 1 $$$l$$$ $$$c_1$$$ $$$c_2$$$, meaning there is a horizontal ship on line $$$l$$$ between columns $$$c_1$$$ and $$$c_2$$$. It is guaranteed that $$$1 \leq l \leq N$$$ and $$$1 \leq c_1 \leq c_2 \leq M$$$.
- 2 $$$c$$$ $$$l_1$$$ $$$l_2$$$, meaning there is a vertical ship on column $$$c$$$ between lines $$$l_1$$$ and $$$l_2$$$. It is guaranteed that $$$1 \leq c \leq M$$$ and $$$1 \leq l_1 \leq l_2 \leq N$$$.
The placements of the ships can intersect each other.
The output file should contain $$$S$$$ lines, each with the state of the corresponding ship.
5 5 3 2 1 2 2 2 2 3 3 3 4 5 4 5 1 2 1 3 1 2 1 4 2 1 3 5 1 3 2 4 2 2 1 5
SUNK HIT MISS SUNK HIT
This problem is similar to DrahSort. Please read the problem statement carefully to understand the differences
You are given an array of $$$N$$$ non-negative integers and a list of $$$Q$$$ operations that need to be performed on it. Each operation can be of the following 2 types:
- $$$1$$$ $$$l$$$ $$$r$$$ $$$(1 \leq l \leq r \leq N)$$$ - sort the contiguous subsequence $$$[l, r]$$$ of the array
- $$$2$$$ $$$l$$$ $$$r$$$ $$$(1 \leq l \leq r \leq N)$$$ - find the minimum required cost to sort the contiguous subsequence $$$[l, r]$$$ of the array
All first type operations will not contain any partially intersecting substrings. In other words, for every pair of updates $$$1$$$ $$$l1$$$ $$$r1$$$ and $$$1$$$ $$$l2$$$ $$$r2$$$, one of the following conditions will always be true:
- $$$r1 \lt l2$$$
- $$$r2 \lt l1$$$
- $$$l1 \leq l2 \leq r2 \leq r1$$$
- $$$l2 \leq l1 \leq r1 \leq r2$$$
The cost required to sort a substring, $$$[l, r]$$$ ($$$1 \leq l \leq r \leq N$$$), is defined as follows. You are only allowed to swap consecutive elements from the substring (any pair of indices $$$(i, i + 1)$$$ such that $$$l \leq i \leq r - 1$$$). The cost of swapping two consecutive elements is the product of the elements being swapped. The cost of sorting the entire substring is defined as the maximum cost among each individual swap.
Please note that the operations of the first type are persistent and will alter the structure of the array, while the operations of the second type won't perform any changes on it.
The first line of input will contain one integer $$$N$$$ ($$$1\leq N \leq 5 \cdot 10^4$$$), representing the number of elements of the array.
The second line of input will contain $$$N$$$ integers ($$$0 \leq A[i] \leq 10^9$$$, $$$1\leq i \leq N$$$), the elements of the array.
The third line of input will contain one integer $$$Q$$$ ($$$1\leq Q \leq 5 \cdot 10^4$$$), representing the number of operations.
Each of the following $$$Q$$$ lines will contain one operation as described in the problem statement.
For every query of the second type output the required cost to sort the substring.
10 10 9 8 7 6 5 4 3 2 1 11 1 1 2 2 1 2 2 1 3 2 1 10 2 9 10 1 3 4 2 1 4 2 3 4 2 2 3 1 1 4 2 1 4
0 80 80 2 80 0 70 0
1. After the first update the array looks as follows
9 10 8 7 6 5 4 3 2 1
2. For the second query we need to find the cost of sorting the substring $$$[1,2]$$$ which is 0, because the substring is already sorted
3. For the third query we need to find the cost of sorting the substring $$$[1,3]$$$. We need to perform 2 swaps (indices ($$$2$$$, $$$3$$$) cost $$$80$$$ and ($$$1$$$, $$$2$$$) cost 72). Hence the cost will be $$$80$$$
As previously mentioned in the statement, the array won't change after this query.
etc.