HackerEarth Retroactive Integers problem solution

YASH PAL,
In this HackerEarth Retroactive Integers problem solution You’re maintaining 20 variables: a,b,c,…,r,s,t. At any moment of the time value of any variable is an 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. “? x” print value of variable x.
  2. ” = x y” write value of variable y to variable x.
  3. “! x c” set variable x to c.
  4. ” + x c” add c to variable x.
  5. “* 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.
HackerEarth Retroactive Integers problem solution

HackerEarth Retroactive Integers problem solution.

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;
typedef long long ll;

const int M = 200100;
const int N = 6;
const int mod = 1e9 + 7;

int add(int x, int y) {
  x += y;
  if (x >= mod)
    x -= mod;
  return x;
}

int udd(int &x, int y) {
  return x = add(x, y);
}

int mul(ll x, ll y) {
  return x * y % mod;
}

struct Matrix {
  int a[N][N];

  Matrix() {
    for (int i = 0; i < N; ++i)
      fill(a[i], a[i] + N, 0);
  }

  int* operator[](int x) {
    return a[x];
  }

  Matrix operator*(Matrix to) {
    Matrix ans;
    for (int i = 0; i < N; ++i)
      for (int k = 0; k < N; ++k)
        for (int j = 0; j < N; ++j)
          udd(ans[i][j], mul(a[i][k], to[k][j]));
    return ans;
  }
} I;


int q, x[M], xs[M];
char type[M];
int from[M], to[M], by[M];
Matrix t[4 * M];

void ini() {
  for (int i = 0; i < N; ++i)
    I[i][i] = 1;
  fill(t, t + (4 * M), I);
}

int readVariable() {
  char c;
  cin >> c;
  return c - 'a' + 1;
}

void read() {
  cin >> q;
  for (int i = 0; i < q; ++i) {
    cin >> x[i];
    xs[i] = x[i];

    cin >> type[i];
    if (type[i] == '?') {
      from[i] = readVariable();
    } else if (type[i] == '=') {
      to[i] = readVariable();
      from[i] = readVariable();
      by[i] = 1;
    } else if (type[i] == '!') {
      to[i] = readVariable();
      from[i] = 0;
      cin >> by[i];
    } else if (type[i] == '+') {
      to[i] = readVariable();
      from[i] = 0;
      cin >> by[i];
    } else if (type[i] == '*') {
      to[i] = readVariable();
      from[i] = to[i];
      cin >> by[i];
    } else {
      cerr << "i = " << i << endl;
      cerr << "type = " << type[i] << endl;
      assert(false);
    }
  }
}

void comp() {
  sort(xs, xs + q);
  for (int i = 0; i < q; ++i)
    x[i] = lower_bound(xs, xs + q, x[i]) - xs;
}


Matrix get(int v, int l, int r, int at) {
  assert(l <= at && at < r);
  if (l + 1 == r) {
    return t[v];
  }
  int m = (l + r) / 2;
  if (at < m)
    return get(2 * v, l, m, at);
  else {
    return t[2 * v] * get(2 * v + 1, m, r, at);
  }
}

void upd(int v, int l, int r, int at, Matrix &A) {
  assert(l <= at && at < r);
  if (l + 1 == r) {
    t[v] = A;
    return;
  }
  int m = (l + r) / 2;
  if (at < m)
    upd(2 * v, l, m, at, A);
  else
    upd(2 * v + 1, m, r, at, A);
  t[v] = t[2 * v] * t[2 * v + 1];
}

void kill() {
  for (int i = 0; i < q; ++i) {
    int at = x[i];
    if (type[i] == '?') {
      Matrix A = get(1, 0, q, at);
      cout << A[0][from[i]] << "n";
    } else {
      Matrix A = I;
      if (type[i] != '+' && type[i] != '*') {
        A[to[i]][to[i]] = 0;
      }
      A[from[i]][to[i]] = by[i];
      upd(1, 0, q, at, A);
    }
  }
}

int main() {
#ifdef LOCAL
  assert(freopen("a.in", "r", stdin));
#endif

  ios_base::sync_with_stdio(false);

  ini();
  read();
  comp();
  kill();
}

Second solution

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        RetroactiveIntegers solver = new RetroactiveIntegers();
        solver.solve(1, in, out);
        out.close();
    }

    static class RetroactiveIntegers {
        public static int mod = 1000000007;
        public static int w = 15;

        public static int[][] getIdentity(int n) {
            int[][] res = new int[w][3];
            for (int i = 0; i < w; i++) {
                res[i][0] = i;
                res[i][1] = 1;
            }
            return res;
        }

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int q = in.nextInt();
            RetroactiveIntegers.Query[] qs = new RetroactiveIntegers.Query[q];
            int[] times = new int[q];
            for (int i = 0; i < q; i++) {
                qs[i] = new RetroactiveIntegers.Query(in, i);
                times[i] = qs[i].time;
            }
            Arrays.sort(times);
            for (int i = 0; i < q; i++) {
                qs[i].time = Arrays.binarySearch(times, qs[i].time);
            }
            RetroactiveIntegers.SegmentTree os = new RetroactiveIntegers.SegmentTree(q);
            for (int i = 0; i < q; i++) {
                if (qs[i].which != -1) {
                    int[][] x = os.query(0, qs[i].time);
                    out.println(x[qs[i].which][2]);
                } else {
                    os.modify(qs[i].time, qs[i].vv);
                }
            }
        }

        public static int[][] combine(int[][] a, int[][] b) {
            int[][] ret = new int[w][3];
            for (int i = 0; i < w; i++) {
                int tt = b[i][0];
                ret[i][0] = a[tt][0];
                ret[i][1] = (int) ((1L * a[tt][1] * b[i][1]) % mod);
                ret[i][2] = (int) ((1L * a[tt][2] * b[i][1] + b[i][2]) % mod);
            }
            return ret;
        }

        static class Query {
            public int time;
            public int idx;
            public int[][] vv;
            public int which;

            public Query(InputReader in, int idx) {
                this.idx = idx;
                time = in.nextInt();
                char c = in.next().charAt(0);
                vv = new int[w][3];
                for (int i = 0; i < w; i++) {
                    vv[i][0] = i;
                    vv[i][1] = 1;
                }
                which = -1;
                switch (c) {
                    case '?': {
                        which = in.next().charAt(0) - 'a';
                        break;
                    }
                    case '=': {
                        int a1 = in.next().charAt(0) - 'a';
                        int a2 = in.next().charAt(0) - 'a';
                        vv[a1][0] = a2;
                        break;
                    }
                    case '*': {
                        int a = in.next().charAt(0) - 'a';
                        int m = in.nextInt();
                        vv[a][1] = m;
                        break;
                    }
                    case '!': {
                        int a = in.next().charAt(0) - 'a';
                        int m = in.nextInt();
                        vv[a][1] = 0;
                        vv[a][2] = m;
                        break;
                    }
                    case '+': {
                        int a = in.next().charAt(0) - 'a';
                        int m = in.nextInt();
                        vv[a][2] = m;
                        break;
                    }
                }
            }

        }

        static class SegmentTree {
            int n;
            int[][][] value;

            public SegmentTree(int n) {
                this.n = n;
                value = new int[4 * n][][];
                init(0, 0, n - 1);
            }

            void init(int root, int left, int right) {
                value[root] = getIdentity(w);
                if (left != right) {
                    init(2 * root + 1, left, (left + right) / 2);
                    init(2 * root + 2, (left + right) / 2 + 1, right);
                }
            }

            public int[][] query(int from, int to) {
                return query(from, to, 0, 0, n - 1);
            }

            int[][] query(int from, int to, int root, int left, int right) {
                if (from == left && to == right)
                    return value[root];
                int mid = (left + right) >> 1;
                if (from <= mid && to > mid)
                    return combine(
                            query(from, Math.min(to, mid), root * 2 + 1, left, mid),
                            query(Math.max(from, mid + 1), to, root * 2 + 2, mid + 1, right));
                else if (from <= mid)
                    return query(from, Math.min(to, mid), root * 2 + 1, left, mid);
                else if (to > mid)
                    return query(Math.max(from, mid + 1), to, root * 2 + 2, mid + 1, right);
                else
                    throw new RuntimeException("Incorrect query from " + from + " to " + to);
            }

            public void modify(int pos, int[][] nv) {
                modify(pos, nv, 0, 0, n - 1);
            }

            void modify(int pos, int[][] nv, int root, int left, int right) {
                if (pos == left && pos == right) {
                    value[root] = nv;
                    return;
                }
                int mid = (left + right) >> 1;
                if (pos <= mid)
                    modify(pos, nv, 2 * root + 1, left, mid);
                if (pos > mid)
                    modify(pos, nv, 2 * root + 2, mid + 1, right);
                value[root] = combine(value[2 * root + 1], value[2 * root + 2]);
            }

        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (this.numChars == -1) {
                throw new InputMismatchException();
            } else {
                if (this.curChar >= this.numChars) {
                    this.curChar = 0;

                    try {
                        this.numChars = this.stream.read(this.buf);
                    } catch (IOException var2) {
                        throw new InputMismatchException();
                    }

                    if (this.numChars <= 0) {
                        return -1;
                    }
                }

                return this.buf[this.curChar++];
            }
        }

        public int nextInt() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }

            byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }

            int res = 0;

            while (c >= 48 && c <= 57) {
                res *= 10;
                res += c - 48;
                c = this.read();
                if (isSpaceChar(c)) {
                    return res * sgn;
                }
            }

            throw new InputMismatchException();
        }

        public String next() {
            int c;
            while (isSpaceChar(c = this.read())) {
                ;
            }

            StringBuilder result = new StringBuilder();
            result.appendCodePoint(c);

            while (!isSpaceChar(c = this.read())) {
                result.appendCodePoint(c);
            }

            return result.toString();
        }

        public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void println(int i) {
            writer.println(i);
        }

    }
}
coding problems solutions