Submission #331231

#	Time	Username	Problem	Language	Result	Execution time	Memory
331231		AlexPop28	Lucky Numbers (RMI19_lucky)	C++11	100 / 100	36 ms	11116 KiB

lucky

#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

const int MOD = (int)1e9 + 7;
const int N = (int)1e5 + 10;

template<class T>
struct ModInt {
  T n;
  ModInt(bool n_) : n(n_) {}
  ModInt(T n_ = 0) : n(n_ % MOD) {
    while (n < 0) n += MOD;
  }
  ModInt operator+(const ModInt &other) const { return n + other.n; }
  ModInt operator-(const ModInt &other) const { return n - other.n; }
  ModInt operator*(const ModInt &other) const { return n * other.n; }
  ModInt& operator+=(const ModInt &other) { return *this = *this + other; }
  ModInt& operator-=(const ModInt &other) { return *this = *this - other; }
  ModInt& operator*=(const ModInt &other) { return *this = *this * other; }
  T operator()() { return n; }
};

using Int = ModInt<int64_t>;

Int ways[N];

Int Ways(int n) {
  if (n >= 0) return ways[n];
  return Int((int64_t)0);
}

Int operator*(const bool &x, const Int &y) {
  if (x) return y;
  return Int((int64_t)0);
}

struct Node {
  int len;
  Int dp, dp1, dp3, dp13; // excluding current interval
  bool _dp, _dp1, _dp3, _dp13; // current interval

  Node(int64_t val = 0) {
    len = 1;
    dp = val;
    dp1 = val > 1;
    dp3 = val > 3;
    dp13 = false;
    _dp = true;
    _dp1 = val == 1;
    _dp3 = val == 3;
    _dp13 = false;
  }

  Node operator+(const Node &other) const {
    Node ret;
    ret.len = len + other.len;
    ret.dp = dp * Ways(other.len) - dp1 * Ways(other.len - 1) +
             _dp * other.dp - _dp1 * other.dp3;
    ret.dp1 = dp * Ways(other.len - 1) - dp1 * Ways(other.len - 2) +
              _dp * other.dp1 - _dp1 * other.dp13;
    ret.dp3 = dp3 * Ways(other.len) - dp13 * Ways(other.len - 1) +
              _dp3 * other.dp - _dp13 * other.dp3;
    ret.dp13 = dp3 * Ways(other.len - 1) - dp13 * Ways(other.len - 2) +
                _dp3 * other.dp1 - _dp13 * other.dp13;
              

    ret._dp = _dp && other._dp && (!_dp1 || !other._dp3);
    ret._dp1 = ret._dp && other._dp1;
    ret._dp3 = ret._dp && _dp3;
    ret._dp13 = ret._dp && _dp3 && other._dp1;
    return ret;
  }

  Int Get() {
    return dp + _dp;
  }
};

struct SegmTree {
  int n;
  vector<Node> t;

  SegmTree(const string &s) : n(s.size()), t(2 * n) {
    for (int i = 0; i < n; ++i)
      t[i + n] = Node(s[i] - '0');
    for (int i = n - 1; i >= 1; --i)
      t[i] = t[2 * i] + t[2 * i + 1];
  }

  void Update(int pos, int val) {
    for (t[pos += n] = Node(val); pos /= 2; )
      t[pos] = t[2 * pos] + t[2 * pos + 1];
  }

  Node Query(int l, int r) {
    Node ans_l, ans_r;
    bool fst_l = true, fst_r = true;

    for (l += n, r += n; l < r; l /= 2, r /= 2) {
      if (l & 1) {
        if (fst_l) ans_l = t[l++];
        else ans_l = ans_l + t[l++];
        fst_l = false;
      }
      if (r & 1) {
        if (fst_r) ans_r = t[--r];
        else ans_r = t[--r] + ans_r;
        fst_r = false;
      }
    }

    if (fst_l) return ans_r;
    if (fst_r) return ans_l;
    return ans_l + ans_r;
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  ways[0] = (int64_t)1;
  for (int i = 1; i < N; ++i) {
    ways[i] = ways[i - 1] * Int((int64_t)10);
    if (i - 2 >= 0) ways[i] -= ways[i - 2];
  }
  
//  string s = "14";
//  SegmTree st(s);
//  cout << st.Query(0, 2).Get()() << endl;

  int n, q; cin >> n >> q; cin.get();
  string s; getline(cin, s);
  assert(n == (int)s.length());

  SegmTree st(s);
  cout << st.Query(0, n).Get()() << '\n';
  while (q--) {
    int t; cin >> t;
    if (t == 1) {
      int l, r; cin >> l >> r;
      cout << st.Query(l - 1, r).Get()() << '\n';
    } else {
      int pos, dig; cin >> pos >> dig;
      st.Update(pos - 1, dig);
    }
  }
}

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