Submission #645754

#	Time	Username	Problem	Language	Result	Execution time	Memory
645754		Alex_tz307	Lucky Numbers (RMI19_lucky)	C++17	100 / 100	83 ms	12876 KiB

lucky

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
string s;

void addSelf(int &x, int y) {
  x += y;
  if (x >= mod) {
    x -= mod;
  }
}

int mult(int x, int y) {
  return (int64_t)x * y % mod;
}

struct node {
  int small[2][2];
  int eq[2][2];
  int big[2][2];

  void setLeaf(int c) {
    small[0][0] = c - (c > 1) - (c > 3);
    small[1][0] = (c > 3);
    small[0][1] = (c > 1);
    small[1][1] = 0;

    eq[0][0] = ((c != 1) && (c != 3));
    eq[1][0] = (c == 3);
    eq[0][1] = (c == 1);
    eq[1][1] = 0;

    big[0][0] = 9 - c - (c < 1) - (c < 3);
    big[1][0] = (c < 3);
    big[0][1] = (c < 1);
    big[1][1] = 0;
  }

  node operator + (const node &rhs) const {
    node res;

    for (int left = 0; left <= 1; ++left) {

      for (int right = 0; right <= 1; ++right) {

        res.small[left][right] = 0;
        res.eq[left][right] = 0;
        res.big[left][right] = 0;

        for (int left1 = 0; left1 <= 1; ++left1) {

          for (int right3 = 0; right3 <= 1 - left1; ++right3) {

            addSelf(res.small[left][right], mult(small[left][left1], rhs.small[right3][right]));
            addSelf(res.small[left][right], mult(small[left][left1], rhs.eq[right3][right]));
            addSelf(res.small[left][right], mult(small[left][left1], rhs.big[right3][right]));
            addSelf(res.small[left][right], mult(eq[left][left1], rhs.small[right3][right]));

            addSelf(res.eq[left][right], mult(eq[left][left1], rhs.eq[right3][right]));

            addSelf(res.big[left][right], mult(big[left][left1], rhs.small[right3][right]));
            addSelf(res.big[left][right], mult(big[left][left1], rhs.eq[right3][right]));
            addSelf(res.big[left][right], mult(big[left][left1], rhs.big[right3][right]));
            addSelf(res.big[left][right], mult(eq[left][left1], rhs.big[right3][right]));

          }

        }

      }

    }

    return res;
  }
};

struct ST {
  int n;
  vector<node> t;

  ST(int N) : n(N) {
    int dim = 1;
    while (dim < n) {
      dim *= 2;
    }
    t.resize(dim * 2);
  }

  void build(int x, int lx, int rx) {
    if (lx == rx) {
      t[x].setLeaf(s[lx] - '0');
      return;
    }

    int mid = (lx + rx) / 2;

    build(x * 2, lx, mid);
    build(x * 2 + 1, mid + 1, rx);

    t[x] = t[x * 2] + t[x * 2 + 1];
  }

  void update(int x, int lx, int rx, int pos) {
    if (lx == rx) {
      t[x].setLeaf(s[pos] - '0');
      return;
    }

    int mid = (lx + rx) / 2;

    if (pos <= mid) {
      update(x * 2, lx, mid, pos);
    } else {
      update(x * 2 + 1, mid + 1, rx, pos);
    }

    t[x] = t[x * 2] + t[x * 2 + 1];
  }

  void update(int pos) {
    update(1, 1, n, pos);
  }

  node query(int x, int lx, int rx, int st, int dr) {
    if (st <= lx && rx <= dr) {
      return t[x];
    }

    int mid = (lx + rx) / 2;

    if (st <= mid && mid < dr) {
      return query(x * 2, lx, mid, st, dr) + query(x * 2 + 1, mid + 1, rx, st, dr);
    } else if (st <= mid) {
      return query(x * 2, lx, mid, st, dr);
    } else {
      return query(x * 2 + 1, mid + 1, rx, st, dr);
    }
  }

  node query(int st, int dr) {
    return query(1, 1, n, st, dr);
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, q;
  cin >> n >> q >> s;
  s = '$' + s;

  ST t(n);
  t.build(1, 1, n);

  auto solve = [&](int x, int y) -> int {
    node res = t.query(x, y);

    int ans = 0;

    for (int i = 0; i <= 1; ++i) {
      for (int j = 0; j <= 1; ++j) {
        addSelf(ans, res.small[i][j]);
        addSelf(ans, res.eq[i][j]);
      }
    }

    return ans;
  };

  cout << solve(1, n) << '\n';

  for (int i = 0; i < q; ++i) {
    int op, x, y;
    cin >> op >> x >> y;

    if (op == 1) {
      cout << solve(x, y) << '\n';
    } else if ((s[x] - '0') != y) {
      s[x] = '0' + y;
      t.update(x);
    }
  }
  return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 27 / 27
• Subtask 5: 9 / 9
• Subtask 6: 27 / 27