Variable Lists¶
Estimated time limit: 0.5 seconds. Memory limit: 128 MB.
The deployed limit is twice the largest per-input median runtime of the reference program on the target judge, rounded up to a multiple of \(0.5\) seconds. See the reference measurements.
Story¶
A visual editor keeps a separate list of local variables for each subroutine. Programmers insert and delete variables and edit their notes. Maintain the lists and answer queries about a variable and its neighbors.
Formal Problem Statement¶
There are \(n\) lists. List \(i\) initially contains \(c_i\) variables. Assign consecutive IDs \(1,2,\ldots,C\) by increasing list number and then from front to back within each list, where \(C=\sum_{i=1}^n c_i\) . Each variable's initial note equals its ID.
Support these operations:
| Operation | Meaning |
|---|---|
1 id |
Query the notes of the predecessor, the variable itself and the successor, within its own list. Print NULL for a missing predecessor or successor. If the variable does not exist or was deleted, print three NULL entries. |
2 id |
Delete the variable. Ignore an unassigned ID or an already deleted variable. |
3 nid |
Insert a variable at the front of list nid . |
4 nid |
Insert a variable at the back of list nid . |
5 id x |
Change the variable's note to x . Ignore an unassigned ID or an already deleted variable. |
Every insertion receives a fresh ID equal to the initial number of variables plus the number of insertions so far, including this insertion. Its initial note equals that ID. Deletion never reuses an ID. A list may become empty; inserting at either end of an empty list creates a one-element list. Editing a note does not change the ID.
Node labels are “ID: note”, and arrows indicate neighboring variables within a list. The upper pair shows the initial state of Sample 1; the lower pair shows the state after operation \(8\) .
Input¶
The first line contains \(n\) . The second line contains \(n\) integers \(c_1,\ldots,c_n\) . The third line contains the number of operations \(m\) . Each of the next \(m\) lines describes one operation in the format above.
Output¶
Only 1 id operations produce output. Print three entries for the predecessor, the variable itself and the successor, using the note or NULL as appropriate. Separate entries with one space.
Samples¶
Sample 1¶
Input¶
2
2 1
12
1 2
1 3
5 2 -7
1 1
2 1
1 2
3 1
4 2
1 4
1 5
2 2
1 2
Output¶
1 2 NULL
NULL 3 NULL
NULL 1 -7
NULL -7 NULL
NULL 4 -7
3 5 NULL
NULL NULL NULL
Sample 2¶
Input¶
1
1
9
2 1
1 1
1 2
3 1
1 2
2 2
4 1
1 3
1 0
Output¶
NULL NULL NULL
NULL NULL NULL
NULL 2 NULL
NULL 3 NULL
NULL NULL NULL
Sample 3¶
Input¶
1
2
5
5 1 42
5 2 42
1 1
2 1000000000
1 2
Output¶
NULL 42 42
42 42 NULL
Sample explanations¶
In Sample 1, after ID \(2\) is changed to note \(-7\) , querying ID \(1\) reports the updated successor note. Once ID \(1\) is deleted, ID \(2\) has no predecessor. Sample 2 demonstrates that IDs are never reused. In Sample 3, two variables may have the same note while retaining distinct IDs.
Constraints and guarantees¶
For all inputs: \(1\le n\le500\) , \(1\le c_i\le1000\) , and \(1\le m\le5\times10^5\) . Insertions satisfy \(1\le\mathrm{nid}\le n\) ; IDs and notes in the other operations satisfy \(|\mathrm{id}|,|x|\le10^9\) . Every operation has one of the five listed types.
| Score | Additional conditions |
|---|---|
| 100% | No additional conditions |