Submission #715786

#	Time	Username	Problem	Language	Result	Execution time	Memory
715786		cig32	Crossing (JOI21_crossing)	C++17	100 / 100	1228 ms	24016 KiB

Main

#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 2e5 + 10;
int MOD;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
string gene(string a, string b) {
  string c;
  for(int i=0; i<a.size(); i++) {
    if(a[i] == b[i]) c += a[i];
    else {
      string t = "JOI";
      for(int j=0; j<3; j++) {
        if(a[i] != t[j] && b[i] != t[j]) c += t[j];
      }
    }
  }
  return c;
}
int random_prime(int l, int r) {
  while(1) {
    int x = rnd(l, r);
    int c = 0;
    for(int i=1; i*i<=x; i++) {
      if(x%i == 0) {
        c+=2;
        if(i*i == x) c--;
      }
    }
    if(c==2) return x;
  }
  return 1226;
}
int geometric_sequence_sum(int a, int x, int n) {
  // S = ax^0+ax^1+...+ax^(n-1)
  // xS = ax^1+ax^2+...+ax^n
  // (x-1)S = ax^n-a
  // S = a(x^n-1)/(x-1)
  
  int s = a;
  s *= bm(x, n) - 1;
  s %= MOD;
  s *= inv(x - 1);
  s %= MOD;
  return s;
}
int ans, n;
void add_segment(int l, int r, int v) {
  ans += geometric_sequence_sum(bm(3, n-r-1), 3, r-l+1) * v;
  ans %= MOD;
}
void sub_segment(int l, int r, int v) {
  ans -= geometric_sequence_sum(bm(3, n-r-1), 3, r-l+1) * v;
  ans += (MOD << 1);
  ans %= MOD;
}
void solve(int tc) {
  MOD = random_prime(5e8, 1.25 * 1e9);
  cin >> n;
  string s[9];
  cin >> s[0] >> s[1] >> s[2];
  s[3] = gene(s[0], s[1]);
  s[4] = gene(s[0], s[2]);
  s[5] = gene(s[1], s[2]);
  s[6] = gene(s[2], s[3]);
  s[7] = gene(s[1], s[4]);
  s[8] = gene(s[0], s[5]);
  int h[9];
  for(int i=0; i<9; i++) {
    h[i] = 0;
    for(int j=0; j<n; j++) {
      h[i] = (h[i] * 3 + (s[i][j] == 'J' ? 0 : (s[i][j] == 'O' ? 1 : 2))) % MOD;
    }
  }
  int q;
  cin >> q;
  string def;
  cin >> def;
  for(char c: def) ans = (ans * 3 + (c == 'J' ? 0 : (c == 'O' ? 1 : 2))) % MOD;
  bool yes = 0;
  for(int i=0; i<9; i++) yes |= (ans == h[i]);
  cout << (yes ? "Yes\n" : "No\n");
  set<pair<pair<int,int>,int> > ranges;
  for(int i=0; i<def.size(); i++) {
    int j = i;
    while(j+1 < def.size() && def[j+1] == def[i]) j++;
    ranges.insert({{i, j}, (def[i] == 'J' ? 0 : (def[i] == 'O' ? 1 : 2))});
    i = j;
  }
  for(int i=0; i<q; i++) {
    int l, r;
    cin >> l >> r;
    --l, --r;
    char c;
    cin >> c;
    auto it = ranges.lower_bound({{l, 0}, 0});
    if(it != ranges.begin()) it--;
    vector<pair<pair<int,int>,int> > to_add, to_sub;
    to_add.push_back({{l, r}, (c == 'J' ? 0 : (c == 'O' ? 1 : 2))});
    while(it != ranges.end() && (*it).first.first <= r) {
      if((*it).first.second >= l) { // relevant
        to_sub.push_back(*it);
        if((*it).first.first < l) {
          to_add.push_back({{(*it).first.first, l-1}, (*it).second});
        }
        if((*it).first.second > r) {
          to_add.push_back({{r+1, (*it).first.second}, (*it).second});
        }
      }
      it++;
    }
    for(auto x: to_sub) {
      ranges.erase(x);
      sub_segment(x.first.first, x.first.second, x.second);
    }
    for(auto x: to_add) {
      ranges.insert(x);
      add_segment(x.first.first, x.first.second, x.second);
    }
    bool yes = 0;
    for(int i=0; i<9; i++) {
      if(h[i] == ans) yes = 1;
    }
    cout << (yes ? "Yes\n" : "No\n");
  }

}
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

Compilation message (stderr)

Main.cpp: In function 'std::string gene(std::string, std::string)':
Main.cpp:25:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for(int i=0; i<a.size(); i++) {
      |                ~^~~~~~~~~
Main.cpp: In function 'void solve(long long int)':
Main.cpp:100:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   for(int i=0; i<def.size(); i++) {
      |                ~^~~~~~~~~~~
Main.cpp:102:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     while(j+1 < def.size() && def[j+1] == def[i]) j++;
      |           ~~~~^~~~~~~~~~~~

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