oj.uz

답안 #885092

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
885092 2023-12-09T02:05:12 Z Keys Crossing (JOI21_crossing) C++14
0 / 100
 61 ms 6272 KB 
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define endl '\n'
#define dbg(x) cerr << #x << " = " << x << endl;

typedef vector<int> vi;
typedef vector<string> vs;

const int base = 9973, mod = 1e9 + 7, N = 2e5 + 5;

int n, q, p[N], psum[N], st[N * 4], rset[N * 4];
string a[3], t;
set<int> se;
string joi = "#JOI";

int hash_c(char c) {
  if (c == 'J') return 1;
  else if (c == 'O') return 2;
  else return 3;
}

int hash_s(string s) {
  int ret = 0;
  for (int i = 0; i < int(s.size()); i++) (ret += p[i] * hash_c(s[i]) % mod) %= mod;
  return ret;
}

void pull(int v, int l, int r) {
  int m = (l + r) / 2;
  st[v] = (st[2 * v] + st[2 * v + 1] * p[m - l + 1] % mod) % mod;
}

void push(int v, int l, int r) {
  if (rset[v] == 0) return;
  int m = (l + r) / 2;
  rset[2 * v + 1] = rset[2 * v] = rset[v];
  st[v] = rset[v] * psum[r - l + 1] % mod;
  rset[v] = 0;
}

void build(int v = 1, int l = 0, int r = n - 1) {
  if (l == r) {
    st[v] = hash_c(t[l]);
  } else {
    int m = (l + r) / 2;
    build(v * 2, l, m);
    build(v * 2 + 1, m + 1, r);
    pull(v, l, r);
  }
}

void upd(int ql, int qr, int x, int v = 1, int l = 0, int r = n - 1) {
  if (qr < l or ql > r) return;
  if (l >= ql and r <= qr) {
    rset[v] = x;
    return;
  }
  push(v, l, r);
  int m = (l + r) / 2;
  upd(ql, qr, x, v * 2, l, m);
  upd(ql, qr, x, v * 2 + 1, m + 1, r);
  pull(v, l, r);
}

void comb(vs a) {
  string s = a[0];
  for (int i = 1; i < int(a.size()); i++) {
    string ns = "";
    for (int j = 0; j < n; j++) {
      if (s[j] == a[i][j]) ns += s[j];
      else ns += joi[6 - hash_c(s[j]) - hash_c(a[i][j])];
    }
    s = ns;
  }
  se.insert(hash_s(s));
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  p[0] = 1; for (int i = 1; i < N; i++) p[i] = p[i - 1] * base % mod;
  for (int i = 1; i < N; i++) psum[i] = (psum[i - 1] + p[i - 1]) % mod;
  cin >> n >> a[0] >> a[1] >> a[2] >> q >> t;
  build();
  comb({a[0]}); comb({a[1]}); comb({a[2]}); comb({a[0], a[1]}); comb({a[0], a[2]}); comb({a[1], a[2]});
  comb({a[0], a[1], a[2]}); comb({a[0], a[2], a[1]}); comb({a[1], a[2], a[0]});
  if (se.count(st[1])) cout << "Yes" << endl;
  else cout << "No" << endl;
  while (q--) {
    int l, r; char c; cin >> l >> r >> c; int o = hash_c(c); l--; r--;
    upd(l, r, o);
    if (se.count(st[1])) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
}

Compilation message

Main.cpp: In function 'void push(int64_t, int64_t, int64_t)':
Main.cpp:37:7: warning: unused variable 'm' [-Wunused-variable]
   37 |   int m = (l + r) / 2;
      |       ^

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 6224 KB Output is correct
2 Correct 61 ms 6072 KB Output is correct
3 Correct 60 ms 6272 KB Output is correct
4 Incorrect 52 ms 6200 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 6224 KB Output is correct
2 Correct 61 ms 6072 KB Output is correct
3 Correct 60 ms 6272 KB Output is correct
4 Incorrect 52 ms 6200 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 6224 KB Output is correct
2 Correct 61 ms 6072 KB Output is correct
3 Correct 60 ms 6272 KB Output is correct
4 Incorrect 52 ms 6200 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 6224 KB Output is correct
2 Correct 61 ms 6072 KB Output is correct
3 Correct 60 ms 6272 KB Output is correct
4 Incorrect 52 ms 6200 KB Output isn't correct
5 Halted 0 ms 0 KB -