oj.uz

Submission #494476

# Submission time Handle Problem Language Result Execution time Memory
494476 2021-12-15T14:20:44 Z Pety Lucky Numbers (RMI19_lucky) C++14
100 / 100
 123 ms 26928 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double

using namespace std;

const ll mod = 1e9 + 7;
const ll INF = 1e9;

int n;

struct node {
  bool has13;
  int st, dr;
  int cnt[4][4];
} aint[400002];

int v[100002];

int smaller[100002][4][4], q;

node merge (node fiu1, node fiu2) {
  node p;
  p.has13 = fiu1.has13 | fiu2.has13 | (v[fiu1.dr] == 1 && v[fiu2.st] == 3);
  /// caz1 prima bucata e mai mica
  memset(p.cnt, 0, sizeof(p.cnt));
  for (int i = 1; i <= 3; i++)
    for (int j = 1; j <= 3; j++)
      for (int k = 1; k <= 3; k++)
        for (int t = 1; t <= 3; t++) {
          if (j == 1 && k == 3)
            continue;
          p.cnt[i][t] += 1ll * fiu1.cnt[i][j] * smaller[fiu2.dr - fiu2.st + 1][k][t] % mod;
          // if (fiu1.dr == 2) {
          //   cout << i << " " << t << "\n";
          //   cout << i << " " << j << " " << fiu1.cnt[i][j] << "\n";
          //   cout << k << " " << t << " " << smaller[fiu2.dr - fiu2.st + 1][k][t] << "\n";
          //   cout << 1ll * fiu1.cnt[i][j] * smaller[fiu2.dr - fiu2.st + 1][k][t] << "\n\n";
          // }
          // assert(p.cnt[i][j] >= 0);
          if (p.cnt[i][t] >= mod)
            p.cnt[i][t] -= mod;
        }
  int c1 = v[fiu1.st];
  if (c1 != 1 && c1 != 3) c1 = 2;
  int c2 = v[fiu1.dr];
  if (c2 != 1 && c2 != 3) c2 = 2;
  if (fiu1.has13 == 0)
    for (int i = 1; i <= 3; i++)
      for (int j = 1; j <= 3; j++) {
        if (c2 == 1 && i == 3)
          continue;
        p.cnt[c1][j] += fiu2.cnt[i][j];
        if (p.cnt[c1][j] >= mod)
          p.cnt[c1][j] -= mod;
      }
 // int c3 = v[fiu2.dr];
  //if (c3 != 1 && c3 != 3) c3 = 2;
  //if (!p.has13) {
    //p.cnt[c1][c3]++;
    //if (p.cnt[c1][c3] >= mod) p.cnt[c1][c3] -= mod;
  //}
  p.st = fiu1.st;
  p.dr = fiu2.dr;
  return p;
}

void update (int nod, int st, int dr, int poz, int a) {
  if (st == dr) {
    memset(aint[nod].cnt, 0, sizeof(aint[nod].cnt));
    aint[nod].has13 = 0;
    for (int i = 0; i < a; i++)
      if (i == 1 || i == 3)
        aint[nod].cnt[i][i] = 1;
      else
        aint[nod].cnt[2][2]++;
    return;
  }
  int mid = (st + dr) / 2;
  if (poz <= mid)
    update(2 * nod, st, mid, poz, a);
  else
    update(2 * nod + 1, mid + 1, dr, poz, a);
  aint[nod] = merge(aint[2 * nod], aint[2 * nod + 1]);
}

void build (int nod, int st, int dr) {
  aint[nod].st = st;
  aint[nod].dr = dr;
  if (st == dr) {
    memset(aint[nod].cnt, 0, sizeof(aint[nod].cnt));
    aint[nod].has13 = 0;
    for (int i = 0; i < v[st]; i++)
      if (i == 1 || i == 3)
        aint[nod].cnt[i][i] = 1;
      else
        aint[nod].cnt[2][2]++;
    return;
  }
  int mid = (st + dr) / 2;
  build(2 * nod, st, mid);
  build(2 * nod + 1, mid + 1, dr);
  aint[nod] = merge(aint[2 * nod], aint[2 * nod + 1]);
}

node ans;

void query (int nod, int st, int dr, int a, int b) {
  if (a <= st && dr <= b) {
    if (ans.st == 0) 
      ans = aint[nod];
    else
      ans = merge(ans, aint[nod]);
    return;
  }
  int mid = (st + dr) / 2;
  if (a <= mid)
    query(2 * nod, st, mid, a, b);
  if (mid < b)
    query(2 * nod + 1, mid + 1, dr, a, b);
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n >> q;
  smaller[1][1][1] = 1;
  smaller[1][3][3] = 1;
  smaller[1][2][2] = 8;
  for (int i = 2; i <= n; i++) {
    for (int j = 1; j <= 3; j++)
      for (int k = 1; k <= 3; k++)
        for (int t = 1; t <= 3; t++) {
          if (k == 1 && t == 3)
            continue;
          smaller[i][j][t] += 1ll * smaller[i - 1][j][k] * ((t == 1 || t == 3) ? 1 : 8) % mod;
          if (smaller[i][j][t] >= mod)
            smaller[i][j][t] -= mod;
          //assert(smaller[i][j][t] >= 0);
        }
  }
  string s;
  cin >> s;
  for (int i = 0; i < n; i++)
    v[i + 1] = s[i] - '0';
  build(1, 1, n);
  int sol = 0;
  for (int i = 1; i <= 3; i++)
    for (int j = 1; j <= 3; j++) {
     // assert(aint[1].cnt[i][j] >= 0);
      sol = (sol + aint[1].cnt[i][j]);
      if (sol >= mod) sol -= mod;
    }
  
  cout << (sol + !aint[1].has13) % mod << "\n";
 
  while (q--) {
    int t, x, y;
    cin >> t >> x >> y;
    if (t == 1) {
      ans.st = 0;
      query(1, 1, n, x, y);
      int sol = 0;
      for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++) {
          sol = (sol + ans.cnt[i][j]);
          if (sol >= mod) sol -= mod;
        }
      cout << (sol + !ans.has13) % mod << "\n";
    }
    else {
      v[x] = y;
      update(1, 1, n, x, y);
    }
  }
  
    
  return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2124 KB Output is correct
2 Correct 39 ms 3460 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2124 KB Output is correct
2 Correct 39 ms 3460 KB Output is correct
3 Correct 101 ms 25400 KB Output is correct
4 Correct 82 ms 25356 KB Output is correct
5 Correct 84 ms 26076 KB Output is correct
6 Correct 95 ms 26760 KB Output is correct
7 Correct 123 ms 26720 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 28 ms 2124 KB Output is correct
8 Correct 39 ms 3460 KB Output is correct
9 Correct 41 ms 2124 KB Output is correct
10 Correct 42 ms 3608 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 28 ms 2124 KB Output is correct
8 Correct 39 ms 3460 KB Output is correct
9 Correct 101 ms 25400 KB Output is correct
10 Correct 82 ms 25356 KB Output is correct
11 Correct 84 ms 26076 KB Output is correct
12 Correct 95 ms 26760 KB Output is correct
13 Correct 123 ms 26720 KB Output is correct
14 Correct 41 ms 2124 KB Output is correct
15 Correct 42 ms 3608 KB Output is correct
16 Correct 87 ms 25520 KB Output is correct
17 Correct 90 ms 25432 KB Output is correct
18 Correct 103 ms 26188 KB Output is correct
19 Correct 100 ms 26924 KB Output is correct
20 Correct 109 ms 26928 KB Output is correct