All Tracks Data Structures Advanced Data Structures Segment Trees Problem

Retroactive Integers
Tag(s):

Data Structures, Matrices, Medium-Hard, Segment Trees

Problem
Editorial
Analytics

You're maintaining 20 variables: \(a, b, c, \dots, r, s, t\). At any moment of time value of any variable is integer between 0 and \(1,000,000,006\), inclusive. All arithmetic operations with variables are modulo \(1,000,000,007\). Initially (at moment 0) all variables are set to 0. At some moments of time, you get queries. Queries have 5 different types:

  1. \(\textrm{"? x"}\) print value of variable x.
  2. \(\textrm{"= x y"}\) write value of variable y to variable x.
  3. \(\textrm{"! x c"}\) set variable x to c.
  4. \(\textrm{"+ x c"}\) add c to variable x.
  5. \(\textrm{"* x c"}\) multiply variable x by c.

Also with each query you are given a positive integer --- time when you need to apply this query to variables. Times can go in arbitrary order. See sample for further clarification.

Input Format:
First line contain one integer q --- number of queries.
Next q lines contains queries. i-th query starts with integer \(t_i\) --- time this query should be made at.
Then one of 5 query goes in format, described in the statement.

Output Format:
For each query of the first time print the corresponding value.

Constraints:
\(1 \leqslant q \leqslant 100,000.\)
\(1 \leqslant t_i \leqslant 1,000,000,000.\)
All \(t_i\) are distinct.
In all queries, \(x, y \in \{a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t \}.\)
Also in all queries \(0 \leqslant c \leqslant 1,000,000,006.\)

Scoring:
20 points
Additionally \(q \leqslant 5,000\).
20 points
Additionally, in all queries, \(x = y = a\).
Also queries only of types \(\textrm{*, +, ?}\) are present.
20 points
Additionally, in all queries \(x, y \in \{a, b, c, d, e\}\).
40 points
No additional constraints.

SAMPLE INPUT
8
10 ? e
20 = b a
30 * b 10
40 + b 1
60 ? b
5 ! a 10
70 ? b
25 ? b
SAMPLE OUTPUT
0
1
101
10
Explanation
  1. No queries added before time \(10\), so value of e is 0.
  2. From moment \(20\), \(b=a\).
  3. From moment \(30\), \(b=10a\).
  4. From moment \(40\), \(b=10a+1\).
  5. At moment \(60\): \(b = 10a + 1 = 10 \cdot 0 + 1 = 1\).
  6. From moment 5, \(a = 10\).
  7. So, at moment \(70\), \(b=10a + 1 = 10\cdot 10 + 1 = 101\) because a changed its value at moment 5.
  8. At moment \(25\): \(b = a = 10\).
Time Limit: 7.0 sec(s) for each input file.
Memory Limit: 1024 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

March Clash '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?