oj.uz

Submission #331231

# Submission time Handle Problem Language Result Execution time Memory
331231 2020-11-27T19:14:21 Z AlexPop28 Lucky Numbers (RMI19_lucky) C++11
100 / 100
 36 ms 11116 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 2 ms 1132 KB Output is correct
3 Correct 3 ms 1132 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 2 ms 1132 KB Output is correct
3 Correct 3 ms 1132 KB Output is correct
4 Correct 2 ms 1132 KB Output is correct
5 Correct 2 ms 1132 KB Output is correct
6 Correct 2 ms 1132 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2028 KB Output is correct
2 Correct 15 ms 2284 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2028 KB Output is correct
2 Correct 15 ms 2284 KB Output is correct
3 Correct 24 ms 9068 KB Output is correct
4 Correct 29 ms 9068 KB Output is correct
5 Correct 28 ms 10092 KB Output is correct
6 Correct 30 ms 11116 KB Output is correct
7 Correct 32 ms 11116 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 2 ms 1132 KB Output is correct
3 Correct 3 ms 1132 KB Output is correct
4 Correct 2 ms 1132 KB Output is correct
5 Correct 2 ms 1132 KB Output is correct
6 Correct 2 ms 1132 KB Output is correct
7 Correct 13 ms 2028 KB Output is correct
8 Correct 15 ms 2284 KB Output is correct
9 Correct 12 ms 2028 KB Output is correct
10 Correct 15 ms 2284 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 2 ms 1132 KB Output is correct
3 Correct 3 ms 1132 KB Output is correct
4 Correct 2 ms 1132 KB Output is correct
5 Correct 2 ms 1132 KB Output is correct
6 Correct 2 ms 1132 KB Output is correct
7 Correct 13 ms 2028 KB Output is correct
8 Correct 15 ms 2284 KB Output is correct
9 Correct 24 ms 9068 KB Output is correct
10 Correct 29 ms 9068 KB Output is correct
11 Correct 28 ms 10092 KB Output is correct
12 Correct 30 ms 11116 KB Output is correct
13 Correct 32 ms 11116 KB Output is correct
14 Correct 12 ms 2028 KB Output is correct
15 Correct 15 ms 2284 KB Output is correct
16 Correct 24 ms 9068 KB Output is correct
17 Correct 24 ms 9068 KB Output is correct
18 Correct 29 ms 9964 KB Output is correct
19 Correct 31 ms 10988 KB Output is correct
20 Correct 36 ms 10988 KB Output is correct