oj.uz

Submission #600413

# Submission time Handle Problem Language Result Execution time Memory
600413 2022-07-20T20:22:49 Z Plurm Crossing (JOI21_crossing) C++11
26 / 100
 544 ms 9284 KB 
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9+7;
const int B = 53;
const int invB = 788461544;
int bp[1 << 18];

string sa, sb, sc;
string s, t;

int templ;
void prep(){
  for(char c : s){
    templ = 1ll * templ * B % MOD;
    templ += c;
    templ %= MOD;
  }
}

int seg[1 << 19];
int lb[1 << 19];
int rb[1 << 19];
char lazy[1 << 19];

void build(int c, int l, int r){
  lb[c] = l;
  rb[c] = r;
  if(l == r){
    seg[c] = t[l];
    return;
  }
  int k = (l + r)/2;
  build(2*c, l, k);
  build(2*c+1, k+1, r);
  seg[c] = (1ll * seg[2*c] * bp[r-k] % MOD + seg[2*c+1] % MOD) % MOD;
}

void prop(int c){
  if(lazy[c]){
    seg[c] = 1ll * lazy[c] * ((bp[rb[c] - lb[c] + 1] + MOD - 1) % MOD) % MOD * invB % MOD;
    if(lb[c] != rb[c]){
      lazy[2*c] = lazy[c];
      lazy[2*c+1] = lazy[c];
    }
    lazy[c] = '\0';
  }
}

void update(int c, int l, int r, char x){
  if(lb[c] == l && rb[c] == r) lazy[c] = x;
  prop(c);
  if(lb[c] == l && rb[c] == r) return;
  int k = (lb[c] + rb[c]) /2;
  if(l <= k && k < r){
    update(2*c, l, k, x);
    update(2*c+1, k+1, r, x);
  }else if(r <= k){
    update(2*c, l, r, x);
    prop(2*c+1);
  }else{
    prop(2*c);
    update(2*c+1, l, r, x);
  }
  seg[c] = (1ll * seg[2*c] * bp[rb[c]-k] % MOD + seg[2*c+1] % MOD) % MOD;
}

bool check(){
  prop(1);
  return seg[1] == templ;
}

string cross(string x, string y){
  if(x.empty()) return y;
  else if(y.empty()) return x;
  int n = x.size();
  string ret;
  for(int i = 0; i < n; i++){
    if(x[i] == y[i]) ret.push_back(x[i]);
    else ret.push_back(x[i] ^ y[i] ^ 'J' ^ 'O' ^ 'I');
  }
  return ret;
}

set<string> rec(int left, string cur = ""){
  if(left == 0) return {cur};
  set<string> s = {cur}, t;
  t = rec(left-1, cross(cur, sa));
  s.insert(t.begin(), t.end());
  t = rec(left-1, cross(cur, sb));
  s.insert(t.begin(), t.end());
  t = rec(left-1, cross(cur, sc));
  s.insert(t.begin(), t.end());
  return s;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n >> sa >> sb >> sc;
  int q;
  cin >> q;
  cin >> t;
  if(n <= 100){
    set<string> pool = rec(4);
    cout << (pool.count(t) ? "Yes" : "No") << endl;
    while(q--){
      int l, r;
      char c;
      cin >> l >> r >> c;
      for(int i = l; i <= r; i++){
        t[i-1] = c;
      }
      cout << (pool.count(t) ? "Yes" : "No") << endl;
    }
  }else{
    bp[0] = 1;
    for(int i = 1; i <= n; i++){
      bp[i] = 1ll * bp[i-1] * B % MOD;
    }
    prep();
    build(1, 0, n-1);
    cout << (check() ? "Yes" : "No") << endl;
    while(q--){
      int l, r;
      char c;
      cin >> l >> r >> c;
      update(1, l-1, r-1, c);
      cout << (check() ? "Yes" : "No") << endl;
    }
  }
  
  return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 844 KB Output is correct
2 Correct 302 ms 900 KB Output is correct
3 Correct 357 ms 848 KB Output is correct
4 Correct 290 ms 880 KB Output is correct
5 Correct 267 ms 788 KB Output is correct
6 Correct 260 ms 868 KB Output is correct
7 Correct 271 ms 872 KB Output is correct
8 Correct 308 ms 896 KB Output is correct
9 Correct 308 ms 1000 KB Output is correct
10 Correct 289 ms 804 KB Output is correct
11 Correct 281 ms 888 KB Output is correct
12 Correct 279 ms 888 KB Output is correct
13 Correct 310 ms 900 KB Output is correct
14 Correct 283 ms 888 KB Output is correct
15 Correct 314 ms 904 KB Output is correct
16 Correct 276 ms 892 KB Output is correct
17 Correct 289 ms 912 KB Output is correct
18 Correct 312 ms 1012 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 844 KB Output is correct
2 Correct 302 ms 900 KB Output is correct
3 Correct 357 ms 848 KB Output is correct
4 Correct 290 ms 880 KB Output is correct
5 Correct 267 ms 788 KB Output is correct
6 Correct 260 ms 868 KB Output is correct
7 Correct 271 ms 872 KB Output is correct
8 Correct 308 ms 896 KB Output is correct
9 Correct 308 ms 1000 KB Output is correct
10 Correct 289 ms 804 KB Output is correct
11 Correct 281 ms 888 KB Output is correct
12 Correct 279 ms 888 KB Output is correct
13 Correct 310 ms 900 KB Output is correct
14 Correct 283 ms 888 KB Output is correct
15 Correct 314 ms 904 KB Output is correct
16 Correct 276 ms 892 KB Output is correct
17 Correct 289 ms 912 KB Output is correct
18 Correct 312 ms 1012 KB Output is correct
19 Correct 544 ms 9284 KB Output is correct
20 Correct 500 ms 8824 KB Output is correct
21 Incorrect 493 ms 9148 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 844 KB Output is correct
2 Correct 302 ms 900 KB Output is correct
3 Correct 357 ms 848 KB Output is correct
4 Correct 290 ms 880 KB Output is correct
5 Correct 267 ms 788 KB Output is correct
6 Correct 260 ms 868 KB Output is correct
7 Correct 271 ms 872 KB Output is correct
8 Correct 308 ms 896 KB Output is correct
9 Correct 308 ms 1000 KB Output is correct
10 Correct 289 ms 804 KB Output is correct
11 Correct 281 ms 888 KB Output is correct
12 Correct 279 ms 888 KB Output is correct
13 Correct 310 ms 900 KB Output is correct
14 Correct 283 ms 888 KB Output is correct
15 Correct 314 ms 904 KB Output is correct
16 Correct 276 ms 892 KB Output is correct
17 Correct 289 ms 912 KB Output is correct
18 Correct 312 ms 1012 KB Output is correct
19 Correct 277 ms 884 KB Output is correct
20 Correct 327 ms 916 KB Output is correct
21 Correct 278 ms 836 KB Output is correct
22 Correct 271 ms 2092 KB Output is correct
23 Correct 285 ms 2164 KB Output is correct
24 Correct 263 ms 2200 KB Output is correct
25 Correct 268 ms 2144 KB Output is correct
26 Correct 266 ms 2124 KB Output is correct
27 Correct 291 ms 2184 KB Output is correct
28 Correct 330 ms 2140 KB Output is correct
29 Correct 281 ms 2104 KB Output is correct
30 Correct 260 ms 2080 KB Output is correct
31 Correct 282 ms 2164 KB Output is correct
32 Correct 290 ms 2192 KB Output is correct
33 Correct 275 ms 2088 KB Output is correct
34 Correct 282 ms 2236 KB Output is correct
35 Correct 276 ms 2204 KB Output is correct
36 Correct 284 ms 2128 KB Output is correct
37 Correct 296 ms 2160 KB Output is correct
38 Correct 293 ms 2196 KB Output is correct
39 Correct 304 ms 2164 KB Output is correct
40 Correct 282 ms 2168 KB Output is correct
41 Correct 300 ms 2124 KB Output is correct
42 Correct 297 ms 2096 KB Output is correct
43 Correct 313 ms 2112 KB Output is correct
44 Correct 282 ms 2128 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 844 KB Output is correct
2 Correct 302 ms 900 KB Output is correct
3 Correct 357 ms 848 KB Output is correct
4 Correct 290 ms 880 KB Output is correct
5 Correct 267 ms 788 KB Output is correct
6 Correct 260 ms 868 KB Output is correct
7 Correct 271 ms 872 KB Output is correct
8 Correct 308 ms 896 KB Output is correct
9 Correct 308 ms 1000 KB Output is correct
10 Correct 289 ms 804 KB Output is correct
11 Correct 281 ms 888 KB Output is correct
12 Correct 279 ms 888 KB Output is correct
13 Correct 310 ms 900 KB Output is correct
14 Correct 283 ms 888 KB Output is correct
15 Correct 314 ms 904 KB Output is correct
16 Correct 276 ms 892 KB Output is correct
17 Correct 289 ms 912 KB Output is correct
18 Correct 312 ms 1012 KB Output is correct
19 Correct 544 ms 9284 KB Output is correct
20 Correct 500 ms 8824 KB Output is correct
21 Incorrect 493 ms 9148 KB Output isn't correct
22 Halted 0 ms 0 KB -