Submission #831233

#	Time	Username	Problem	Language	Result	Execution time	Memory
831233		perchuts	Crossing (JOI21_crossing)	C++17	100 / 100	403 ms	35864 KiB

Main

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int ll

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 3e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rnd(int l, int r) {
      uniform_int_distribution<ll> uid(l, r);
      return uid(rng);
}

int pr[maxn][3], seg[4*maxn], lz[4*maxn];

void push(int i, int l, int r) {
      if (lz[i] == 3) return;
      seg[i] = pr[r][lz[i]] ^ pr[l-1][lz[i]];
      if (l != r) lz[2*i] = lz[2*i+1] = lz[i];
      lz[i] = 3;
}

void upd(int i, int l, int r, int x, int y, int k) {
      push(i, l, r);
      if (r < x || y < l) return;
      if (x <= l && r <= y) {
            lz[i] = k;
            push(i, l, r);
            return;
      }
      int md = (l + r) / 2;
      upd(2*i, l, md, x, y, k), upd(2*i+1, md+1, r, x, y, k);
      seg[i] = seg[2*i] ^ seg[2*i+1];
}

int32_t main(){_
      int n; cin >> n; string a, b, c; cin >> a >> b >> c;
      // there are only 27 strings that can be generated (trust)
      map<char, int> f;

      f['J'] = 2, f['O'] = 0, f['I'] = 1;

      for (int i = 0; i < 3; ++i) {
            for (int j = 1; j <= n; ++j) {
                  pr[j][i] = pr[j-1][i] ^ rnd(0, 8e18);
            }
      }

      map<int, bool> existe;

      for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                  for (int k = 0; k < 3; ++k) {
                        int x = 0;
                        if ((i + j + k) % 3 != 1) continue;
                        for (int w = 1; w <= n; ++w) {
                              int ac = f[a[w-1]], bc = f[b[w-1]], cc = f[c[w-1]];
                              int res = (ac * i + bc * j + cc * k) % 3;
                              if (ac == bc && bc == cc) res = ac;
                              x ^= pr[w][res] ^ pr[w-1][res];
                        }
                        existe[x] = 1;
                  }
            }
      }

      for (int i = 1; i < 4*maxn; ++i) lz[i] = 3;

      int q; cin >> q;
      string t; cin >> t;

      for (int i = 1; i <= n; ++i) upd(1, 1, n, i, i, f[t[i-1]]);

      cout << (existe[seg[1]] == 1 ? "Yes" : "No") << endl;

      while (q--) {
            int l, r; char c; cin >> l >> r >> c;
            upd(1, 1, n, l, r, f[c]);
            cout << (existe[seg[1]] == 1 ? "Yes" : "No") << endl;
      }
}

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