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, 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