oj.uz

Submission #600407

# Submission time Handle Problem Language Result Execution time Memory
600407 2022-07-20T20:18:52 Z Plurm Crossing (JOI21_crossing) C++11
3 / 100
 425 ms 17544 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 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;
    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;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n >> s >> s >> s;
  bp[0] = 1;
  for(int i = 1; i <= n; i++){
    bp[i] = 1ll * bp[i-1] * B % MOD;
  }
  prep();
  int q;
  cin >> q;
  cin >> t;
  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 293 ms 2084 KB Output is correct
2 Correct 308 ms 2260 KB Output is correct
3 Correct 386 ms 2156 KB Output is correct
4 Correct 294 ms 2312 KB Output is correct
5 Correct 425 ms 2132 KB Output is correct
6 Correct 360 ms 2072 KB Output is correct
7 Correct 289 ms 2156 KB Output is correct
8 Correct 321 ms 2212 KB Output is correct
9 Correct 339 ms 2216 KB Output is correct
10 Correct 346 ms 2208 KB Output is correct
11 Correct 310 ms 2152 KB Output is correct
12 Correct 317 ms 2120 KB Output is correct
13 Correct 329 ms 2152 KB Output is correct
14 Correct 299 ms 2132 KB Output is correct
15 Correct 306 ms 2124 KB Output is correct
16 Correct 303 ms 2164 KB Output is correct
17 Correct 309 ms 2240 KB Output is correct
18 Correct 328 ms 2272 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 2084 KB Output is correct
2 Correct 308 ms 2260 KB Output is correct
3 Correct 386 ms 2156 KB Output is correct
4 Correct 294 ms 2312 KB Output is correct
5 Correct 425 ms 2132 KB Output is correct
6 Correct 360 ms 2072 KB Output is correct
7 Correct 289 ms 2156 KB Output is correct
8 Correct 321 ms 2212 KB Output is correct
9 Correct 339 ms 2216 KB Output is correct
10 Correct 346 ms 2208 KB Output is correct
11 Correct 310 ms 2152 KB Output is correct
12 Correct 317 ms 2120 KB Output is correct
13 Correct 329 ms 2152 KB Output is correct
14 Correct 299 ms 2132 KB Output is correct
15 Correct 306 ms 2124 KB Output is correct
16 Correct 303 ms 2164 KB Output is correct
17 Correct 309 ms 2240 KB Output is correct
18 Correct 328 ms 2272 KB Output is correct
19 Runtime error 18 ms 17544 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 2084 KB Output is correct
2 Correct 308 ms 2260 KB Output is correct
3 Correct 386 ms 2156 KB Output is correct
4 Correct 294 ms 2312 KB Output is correct
5 Correct 425 ms 2132 KB Output is correct
6 Correct 360 ms 2072 KB Output is correct
7 Correct 289 ms 2156 KB Output is correct
8 Correct 321 ms 2212 KB Output is correct
9 Correct 339 ms 2216 KB Output is correct
10 Correct 346 ms 2208 KB Output is correct
11 Correct 310 ms 2152 KB Output is correct
12 Correct 317 ms 2120 KB Output is correct
13 Correct 329 ms 2152 KB Output is correct
14 Correct 299 ms 2132 KB Output is correct
15 Correct 306 ms 2124 KB Output is correct
16 Correct 303 ms 2164 KB Output is correct
17 Correct 309 ms 2240 KB Output is correct
18 Correct 328 ms 2272 KB Output is correct
19 Correct 301 ms 2200 KB Output is correct
20 Correct 333 ms 2204 KB Output is correct
21 Incorrect 335 ms 2144 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 2084 KB Output is correct
2 Correct 308 ms 2260 KB Output is correct
3 Correct 386 ms 2156 KB Output is correct
4 Correct 294 ms 2312 KB Output is correct
5 Correct 425 ms 2132 KB Output is correct
6 Correct 360 ms 2072 KB Output is correct
7 Correct 289 ms 2156 KB Output is correct
8 Correct 321 ms 2212 KB Output is correct
9 Correct 339 ms 2216 KB Output is correct
10 Correct 346 ms 2208 KB Output is correct
11 Correct 310 ms 2152 KB Output is correct
12 Correct 317 ms 2120 KB Output is correct
13 Correct 329 ms 2152 KB Output is correct
14 Correct 299 ms 2132 KB Output is correct
15 Correct 306 ms 2124 KB Output is correct
16 Correct 303 ms 2164 KB Output is correct
17 Correct 309 ms 2240 KB Output is correct
18 Correct 328 ms 2272 KB Output is correct
19 Runtime error 18 ms 17544 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -