| Submit | All submissions | Best solutions | Back to list |
SPLITS - Split |
Little Petar has been put in charge of maintaining an unpredictable array of strings. Initially, all of the array elements were the same string S, but the array is prone to change; and there is exactly one kind of change that may happen. This is a split operation at a given location, X; after it is performed, the location X maintains the string it had before, however all fields to the left and all fields to the right of X containing the same string as X will be given new strings, S1 and S2.
At certain points in time, Petar will be asked to give the string at a given location. He asked you for help.
Input
The first line of the standard input contains two numbers, N and Q, the size of the array and the total number of operations and queries, respectively.
The second line contains the string S, the string initially contained within each location of the array.
The following Q lines contain the description of either an operation or a query:
A split operation is represented as "SPLIT X S1 S2", implying that the fields to the left of X, containing the same string as at X, will from now on have the string S1, and fields to the right will have the string S2.
A query is represented as "QUERY X", implying that Petar is asked to give the string at location X.
Output
For each QUERY command given, output a new line containing the string currently located on the given position.
Example
Input:
6 6
picsel
SPLIT 3 petarv duxserbia
SPLIT 5 sasav nikolaj
QUERY 1
QUERY 3
QUERY 5
QUERY 6 Output:
petarv
picsel
duxserbia
nikolaj
Explanation
Initially, the string picsel is located throughout the array. After the first and second split operation, respectively, the array looks as follows:
[petarv, petarv, picsel, duxserbia, duxserbia, duxserbia]
[petarv, petarv, picsel, sasav, duxserbia, nikolaj]
The answers to the queries then clearly follow from the final state of the array.
Constraints
- 1 <= N, Q <= 105
- 1 <= X <= N
- 1 <= |S|, |S1|, |S2| <= 50
- The strings will consist solely of lowercase letters of the English alphabet.
- All strings appearing in the operations will be unique.
| Added by: | PetarV |
| Date: | 2015-04-08 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 JS-MONKEY |
| Resource: | Serbian Qualifications 2014 (Own problem) |
hide comments
|
2024-05-28 21:30:43 Simes
I'm with Zukow - there's bad input. I assert "not EOF" before reading a SPLIT or QUERY line and the assertion fires. If I take out the assert, I get WA. I can't figure out what to do when unexpected EOF occurs. I've tried breaking, or re-using the previous valid input, but still WA. |
|
|
2021-11-28 16:56:33 anonymous
Indeed there seems to be something wrong with the test input. I usually configure cin with "std::cin.exceptions(std::ios_base::badbit | std::ios_base::failbit);" to fail fast on I/O errors, but here it results in an abort. Surprisingly, merely ignoring I/O errors gave me an accept verdict :/. Last edit: 2021-11-28 16:57:00 |
|
|
2021-04-19 12:54:43
Zukow, I tested the input and it seems ok. Specifically: - there are no blanklines and there are exactly q query lines, - there are no trailing spaces or multiple adjacent whitespaces, - all query lines begin with "SPLIT" or "QUERY", followed by an integer 0 < x <= n, - for "SPLIT" lines, all s1, s2 strings are of non-zero length and feature only english lowercase chars - for "QUERY" lines, there are no other parameters than integer x Hope that helps. |
|
|
2019-10-19 14:22:15 :D
I'm 99% sure that there is a corrupt input file: a file ending abruptly on one of the strings. I tried pretty much everything here: different I/O routines, trying to control for empty strings, breaking program when EOF is reached, but nothing worked. Can anyone that solved it comment on that? |
RSS