oj.uz

Submission #494475

# Submission time Handle Problem Language Result Execution time Memory
494475 2021-12-15T14:19:35 Z Pety Lucky Numbers (RMI19_lucky) C++14
64 / 100
 108 ms 26996 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 {
      update(1, 1, n, x, y);
      v[x] = y;
    }
  }
  
    
  return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 316 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 31 ms 2128 KB Output is correct
2 Correct 46 ms 3652 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2128 KB Output is correct
2 Correct 46 ms 3652 KB Output is correct
3 Correct 92 ms 25584 KB Output is correct
4 Correct 88 ms 25496 KB Output is correct
5 Correct 94 ms 26252 KB Output is correct
6 Correct 108 ms 26940 KB Output is correct
7 Correct 104 ms 26996 KB Output is correct

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 316 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 31 ms 2128 KB Output is correct
8 Correct 46 ms 3652 KB Output is correct
9 Incorrect 37 ms 2212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 316 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 31 ms 2128 KB Output is correct
8 Correct 46 ms 3652 KB Output is correct
9 Correct 92 ms 25584 KB Output is correct
10 Correct 88 ms 25496 KB Output is correct
11 Correct 94 ms 26252 KB Output is correct
12 Correct 108 ms 26940 KB Output is correct
13 Correct 104 ms 26996 KB Output is correct
14 Incorrect 37 ms 2212 KB Output isn't correct
15 Halted 0 ms 0 KB -