Submission #549757

#	Time	Username	Problem	Language	Result	Execution time	Memory
549757		MilosMilutinovic	Crossing (JOI21_crossing)	C++14	100 / 100	305 ms	14344 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 200005;
const int MD = 1e9 + 7;
const int BASE = 77777;

int mul(int x, int y) {
  return (long long) x * y % MD;
}

int add(int x, int y) {
  return x + y >= MD ? x + y - MD : x + y;
}

int sub(int x, int y) {
  return x - y < 0 ? x - y + MD : x - y;
}

int st[4 * N], lzy[4 * N], pw[N], pref[N];
bool act[4 * N];

void build(int node, int l, int r, string& s) {
  if (l == r) {
    st[node] = mul((s[l] - '0'), pw[l]);
    return;
  }
  int mid = l + r >> 1;
  build(node + node, l, mid, s);
  build(node + node + 1, mid + 1, r, s);
  st[node] = add(st[node + node], st[node + node + 1]);
}

void push(int node, int l, int r) {
  if (!act[node]) {
    return;
  }
  if (l != r) {
    int mid = l + r >> 1;
    st[node + node] = mul(lzy[node], sub(pref[mid], (l == 0 ? 0 : pref[l - 1])));
    st[node + node + 1] = mul(lzy[node], sub(pref[r], pref[mid]));
    lzy[node + node] = lzy[node];
    lzy[node + node + 1] = lzy[node];
    act[node + node] = true;
    act[node + node + 1] = true;
  }
  act[node] = false;
}

void modify(int node, int l, int r, int ll, int rr, char cc) {
  if (l > r || l > rr || r < ll) return;
  if (ll <= l && r <= rr) {
    st[node] = mul(cc - '0', sub(pref[r], (l == 0 ? 0 : pref[l - 1])));
    lzy[node] = cc - '0';
    act[node] = true;
    return;
  }
  push(node, l, r);
  int mid = l + r >> 1;
  modify(node + node, l, mid, ll, rr, cc);
  modify(node + node + 1, mid + 1, r, ll, rr, cc);
  st[node] = add(st[node + node], st[node + node + 1]);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  pw[0] = 1;
  pref[0] = 1;
  for (int i = 1; i < N; i++) {
    pw[i] = mul(pw[i - 1], BASE);
    pref[i] = add(pref[i - 1], pw[i]);
  }
  int n;
  cin >> n;
  string sa, sb, sc;
  cin >> sa >> sb >> sc;
  for (int i = 0; i < n; i++) {
    sa[i] = (sa[i] == 'J' ? '0' : (sa[i] == 'O' ? '1' : '2'));
    sb[i] = (sb[i] == 'J' ? '0' : (sb[i] == 'O' ? '1' : '2'));
    sc[i] = (sc[i] == 'J' ? '0' : (sc[i] == 'O' ? '1' : '2'));
  }
  auto Cross = [&](string s, string t) {
    string res = "";
    for (int i = 0; i < n; i++) {
      if (s[i] == t[i]) {
        res += s[i];
      } else {
        res += (s[i] ^ t[i] ^ '0' ^ '1' ^ '2');
      }
    }
    return res;
  };
  vector<string> a;
  a.push_back(sa);
  a.push_back(sb);
  a.push_back(sc);
  a.push_back(Cross(sa, sb));
  a.push_back(Cross(sa, sc));
  a.push_back(Cross(sb, sc));
  a.push_back(Cross(sa, Cross(sb, sc)));
  a.push_back(Cross(sb, Cross(sa, sc)));
  a.push_back(Cross(sc, Cross(sb, sa)));
  set<int> hsh;
  auto GetHash = [&](string s) {
    int res = 0;
    for (int i = 0; i < n; i++) {
      res = add(res, mul(s[i] - '0', pw[i]));
    }
    return res;
  };
  for (auto &str : a) {
    hsh.insert(GetHash(str));
  }
  int q;
  cin >> q;
  string t;
  cin >> t;
  for (int i = 0; i < n; i++) {
    t[i] = (t[i] == 'J' ? '0' : (t[i] == 'O' ? '1' : '2'));
  }
  build(1, 0, n - 1, t);
  function<void()> Answer = [&]() {
    int my = st[1];
    bool ok = false;
    for (auto he : hsh) {
      ok |= (he == my);
    }
    cout << (ok ? "Yes" : "No") << '\n';
  };
  Answer();
  while (q--) {
    int l, r;
    char foo;
    cin >> l >> r >> foo;
    --l; --r;
    foo = (foo == 'J' ? '0' : (foo == 'O' ? '1' : '2'));
    modify(1, 0, n - 1, l, r, foo);
    Answer();
  }
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void build(int, int, int, std::string&)':
Main.cpp:29:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'void push(int, int, int)':
Main.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function 'void modify(int, int, int, int, int, char)':
Main.cpp:60:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |   int mid = l + r >> 1;
      |             ~~^~~

• Subtask 1: 3 / 3
• Subtask 2: 23 / 23
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51