Submission #537841

#	Time	Username	Problem	Language	Result	Execution time	Memory
537841		cadmiumsky	Crossing (JOI21_crossing)	C++14	0 / 100	438 ms	37020 KiB

Main

#include <bits/stdc++.h>
#define ll long long
using namespace std;

#define int long long
#define hash uhasfsfjha
const int nmax = 2e5 + 5;
const int mod = 998244353;
int p[2][nmax];
struct hash {
  int v[2] = {0, 0};
  int len = 0;
  hash() {;}
  hash(int ch) {v[0] = ch, v[1] = ch, len = 1;}
  hash(int a, int b, int c) {v[0] = a, v[1] = b, len = c;}
  hash operator +(const hash& x) const {
    return hash(v[0] * p[0][x.len] + x.v[0], v[1] * p[1][x.len] + x.v[1], len + x.len);
  }
  ll operator()() const {
    return v[0] * mod + v[1];
  }
};
hash contr[3][nmax];
void inithash(int _0, int _1) {
  p[0][0] = p[0][1] = 1;
  p[0][1] = _0;
  p[1][1] = _1;
  for(int i = 2; i < nmax; i++) {
    p[0][i] = p[0][i - 1] * p[0][1] % mod;
    p[1][i] = p[1][i - 1] * p[1][1] % mod;
  }
  contr[0][1] = hash(0);
  contr[1][1] = hash(1);
  contr[2][1] = hash(2);
  for(int i = 2; i < nmax; i++) {
    for(int j = 0; j < 3; j++)
      contr[j][i] = contr[j][i - 1] + contr[j][1];
  }
}
#undef int

unordered_set<int> freq;
int code(tuple<int,int,int> pp) {
  int x, y, z;
  tie(x, y, z) = pp;
  return x * 3 * 3 + y * 3 + z;
}
void decode(int x, int *to) {
  to[0] = (x % 3), x /= 3, to[1] = (x % 3), x /= 3, to[2] = (x % 3);
  return; 
}
#define stack mata
vector<int> stack;
void insert(int x) { if(!freq.count(x)) freq.insert(x), stack.push_back(x); }
void start() {
  insert(9);
  insert(3);
  insert(1);
  while(stack.size()) {
    int a[3], b[3];
    decode(stack.back(), a);
    stack.pop_back();
    for(auto x : freq) {
      decode(x, b);
      insert(code({(-a[0] + -b[0] + 6) % 3, (-a[1] + -b[1] + 6) % 3, (-a[2] + -b[2] + 6) % 3}));
    }
  }
}

int starter[3][nmax];
int v[nmax];
unordered_set<ll> cine;
int n;

namespace AINT {
  hash aint[nmax * 4];
  int lazy[nmax * 4];
  void apply(int node, int cl, int cr) {
    if(lazy[node] == -1)
      return;
    aint[node] = contr[lazy[node]][cr - cl + 1];
    if(cl == cr)
      return;
    lazy[2 * node] = lazy[node];
    lazy[2 * node + 1] = lazy[node];
    lazy[node] = -1;
  } 
  void prop(int node, int cl, int cr) {
    apply(node, cl, cr);
    if(cl == cr)
      return;
    int mid = cl + cr >> 1;
    apply(2 * node, cl, mid);
    apply(2 * node + 1, mid + 1, cr);
  }
  void upd(int val, int l, int r, int node = 1, int cl = 1, int cr = n) {
    if(l <= cl && cr <= r) {
      lazy[node] = val;
      prop(node, cl, cr);
      return;
    }
    prop(node, cl, cr);
    if(r < cl || cr < l)
      return;
    int mid = cl + cr >> 1;
    upd(val, l, r, 2 * node, cl, mid);
    upd(val, l, r, 2 * node + 1, mid + 1, cr);
    aint[node] = aint[2 * node] + aint[2 * node + 1];
  }
  hash constr(int node = 1, int cl = 1, int cr = n) {
    lazy[node] = -1;
    if(cl == cr)
      return (aint[node] = v[cl]);
    int mid = cl + cr >> 1;
    return aint[node] = constr(node * 2, cl, mid) + constr(2 * node + 1, mid + 1, cr);
  }
  bool query() {
    //cerr << aint[1]() << '\n';
    return cine.count(aint[1]());
  }
};

int encr[256];

int main() {
  encr['O'] = 0;
  encr['J'] = 1;
  encr['I'] = 2;
  char ch;
  inithash(29, 101);
  start();
  cin >> n;
  for(int t = 0; t < 3; t++) {
    for(int i = 1; i <= n; i++) {
      cin >> ch;
      starter[t][i] = encr[ch];
    }
  }
  for(auto x : freq) {
    int aggr[3];
    aggr[0] = x % 3;
    x /= 3;
    aggr[1] = x % 3;
    x /= 3;
    aggr[2] = x % 3;
    hash rez;
    for(int i = 1; i <= n; i++) {
      int y = 0;
      for(int t = 0; t < 3; t++)
        y += aggr[t] * starter[t][i];
      y = (y % 3 + 3) % 3;
      rez = rez + hash(y);
    }
    cine.insert(rez());
  }
  int q;
  cin >> q;
  for(int i = 1; i <= n; i++)
    cin >> ch, v[i] = encr[ch];
  AINT::constr();
  cout << (AINT::query()? "Yes\n" : "No\n");
  for(int i = 0, l, r; i < q; i++) {
    cin >> l >> r >> ch;
    AINT::upd(encr[ch], l, r);
    cout << (AINT::query()? "Yes\n" : "No\n");
  }
}

Compilation message (stderr)

Main.cpp: In function 'void AINT::prop(int, int, int)':
Main.cpp:92:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
Main.cpp: In function 'void AINT::upd(int, int, int, int, int, int)':
Main.cpp:105:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
Main.cpp: In function 'uhasfsfjha AINT::constr(int, int, int)':
Main.cpp:114:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
Main.cpp: In function 'int main()':
Main.cpp:136:28: warning: array subscript has type 'char' [-Wchar-subscripts]
  136 |       starter[t][i] = encr[ch];
      |                            ^~
Main.cpp:159:28: warning: array subscript has type 'char' [-Wchar-subscripts]
  159 |     cin >> ch, v[i] = encr[ch];
      |                            ^~
Main.cpp:164:20: warning: array subscript has type 'char' [-Wchar-subscripts]
  164 |     AINT::upd(encr[ch], l, r);
      |                    ^~

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