oj.uz

Submission #436408

# Submission time Handle Problem Language Result Execution time Memory
436408 2021-06-24T13:22:57 Z Blagojce Crossing (JOI21_crossing) C++11
26 / 100
 1872 ms 1048580 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;
 
mt19937 _rand(time(NULL));
const int mxn = 2e5 + 5;

ll A = 911382323;
ll B = 972663749;


ll pre[3][mxn];


ll seg[4*mxn];
int z[4*mxn];


ll p[mxn];


char alp[3] = {'O', 'I', 'J'};
void upd(int k, int l, int r){
	if(z[k] != 0){
		seg[k] = pre[z[k]-1][r-l+1];
	}
	else{
		int mid = (l+r)/2;
		seg[k] = (((seg[k*2] * p[r-mid]) % B) + seg[k*2+1])%B;
	}
}

void push(int k){
	if(z[k] == 0) return;
	z[k*2] = z[k*2+1] = z[k];
	z[k] = 0;
}

void update(int k, int l, int r, int x, int y, int c){
	if(r < x || l < y){
		if(z[k] != 0) upd(k, l, r);
		return;	
	}
	if(x <= l && r <= x){
		z[k] = c;
		upd(k, l, r);
		return;
	}
	push(k);
	int mid = (l+r)/2;
	update(k*2, l, mid, x, y, c);
	update(k*2+1, mid+1, r, x, y, c);
	upd(k, l, r);
}
 


int n;
string s[mxn];


unordered_map<string, bool> dict;


bool cross(string a, string b, int &m){
	string ns;
	ns.resize(n);
	
	fr(i, 0, n){
		if(a[i] == b[i]){
			ns[i] = a[i];
		}
		else{
			fr(j, 0, 3){
				if(alp[j] != a[i] && alp[j] != b[i]){
					ns[i] = alp[j];
					break;
				}
			}
		}
	}
	if(!dict[ns]){
		dict[ns] = true;
		s[m++] = ns;
		return true;
	}
	return false;
}

void solve(){
	cin >> n;
	fr(i, 0, 3){
		cin >> s[i];
	}
	int m = 3;
	for(int i = 1; i < m; i ++){
		fr(j, 0, i){
			cross(s[i], s[j], m);
		}
	}
	int q;
	
	string t;
	
	cin >> q;
	cin >> t;
	if(dict[t]) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	while(q--){
		int l, r;
		char C;
		cin >> l >> r >> C;
		fr(i, l-1, r) t[i] = C;
		if(dict[t]) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	
	
}

int main(){
	p[0] = 1;
	fr(i, 1, mxn){
		p[i] = (p[i-1]*A) % B;
	}
	fr(k, 0, 3){
		pre[k][0] = 1;
		fr(i, 1, mxn){
			pre[k][i] = (pre[k][i-1]*A + (int)alp[k])%B;
		}
	}
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 39568 KB Output is correct
2 Correct 533 ms 44260 KB Output is correct
3 Correct 514 ms 25588 KB Output is correct
4 Correct 536 ms 44092 KB Output is correct
5 Correct 523 ms 44516 KB Output is correct
6 Correct 533 ms 42212 KB Output is correct
7 Correct 512 ms 40764 KB Output is correct
8 Correct 608 ms 45184 KB Output is correct
9 Correct 591 ms 43928 KB Output is correct
10 Correct 583 ms 49436 KB Output is correct
11 Correct 591 ms 45964 KB Output is correct
12 Correct 577 ms 49644 KB Output is correct
13 Correct 530 ms 46016 KB Output is correct
14 Correct 574 ms 49492 KB Output is correct
15 Correct 542 ms 46000 KB Output is correct
16 Correct 599 ms 49564 KB Output is correct
17 Correct 540 ms 46012 KB Output is correct
18 Correct 475 ms 20512 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 39568 KB Output is correct
2 Correct 533 ms 44260 KB Output is correct
3 Correct 514 ms 25588 KB Output is correct
4 Correct 536 ms 44092 KB Output is correct
5 Correct 523 ms 44516 KB Output is correct
6 Correct 533 ms 42212 KB Output is correct
7 Correct 512 ms 40764 KB Output is correct
8 Correct 608 ms 45184 KB Output is correct
9 Correct 591 ms 43928 KB Output is correct
10 Correct 583 ms 49436 KB Output is correct
11 Correct 591 ms 45964 KB Output is correct
12 Correct 577 ms 49644 KB Output is correct
13 Correct 530 ms 46016 KB Output is correct
14 Correct 574 ms 49492 KB Output is correct
15 Correct 542 ms 46000 KB Output is correct
16 Correct 599 ms 49564 KB Output is correct
17 Correct 540 ms 46012 KB Output is correct
18 Correct 475 ms 20512 KB Output is correct
19 Runtime error 1872 ms 1048580 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 39568 KB Output is correct
2 Correct 533 ms 44260 KB Output is correct
3 Correct 514 ms 25588 KB Output is correct
4 Correct 536 ms 44092 KB Output is correct
5 Correct 523 ms 44516 KB Output is correct
6 Correct 533 ms 42212 KB Output is correct
7 Correct 512 ms 40764 KB Output is correct
8 Correct 608 ms 45184 KB Output is correct
9 Correct 591 ms 43928 KB Output is correct
10 Correct 583 ms 49436 KB Output is correct
11 Correct 591 ms 45964 KB Output is correct
12 Correct 577 ms 49644 KB Output is correct
13 Correct 530 ms 46016 KB Output is correct
14 Correct 574 ms 49492 KB Output is correct
15 Correct 542 ms 46000 KB Output is correct
16 Correct 599 ms 49564 KB Output is correct
17 Correct 540 ms 46012 KB Output is correct
18 Correct 475 ms 20512 KB Output is correct
19 Correct 522 ms 42836 KB Output is correct
20 Correct 518 ms 25524 KB Output is correct
21 Correct 564 ms 48880 KB Output is correct
22 Correct 487 ms 36440 KB Output is correct
23 Correct 566 ms 48800 KB Output is correct
24 Correct 573 ms 43588 KB Output is correct
25 Correct 600 ms 48744 KB Output is correct
26 Correct 495 ms 37820 KB Output is correct
27 Correct 580 ms 48732 KB Output is correct
28 Correct 523 ms 43628 KB Output is correct
29 Correct 539 ms 44868 KB Output is correct
30 Correct 531 ms 37152 KB Output is correct
31 Correct 625 ms 48820 KB Output is correct
32 Correct 633 ms 48736 KB Output is correct
33 Correct 604 ms 45368 KB Output is correct
34 Correct 484 ms 40256 KB Output is correct
35 Correct 573 ms 49536 KB Output is correct
36 Correct 544 ms 46080 KB Output is correct
37 Correct 569 ms 49588 KB Output is correct
38 Correct 529 ms 46068 KB Output is correct
39 Correct 585 ms 49644 KB Output is correct
40 Correct 564 ms 46048 KB Output is correct
41 Correct 551 ms 49540 KB Output is correct
42 Correct 547 ms 45944 KB Output is correct
43 Correct 510 ms 41668 KB Output is correct
44 Correct 528 ms 45272 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 39568 KB Output is correct
2 Correct 533 ms 44260 KB Output is correct
3 Correct 514 ms 25588 KB Output is correct
4 Correct 536 ms 44092 KB Output is correct
5 Correct 523 ms 44516 KB Output is correct
6 Correct 533 ms 42212 KB Output is correct
7 Correct 512 ms 40764 KB Output is correct
8 Correct 608 ms 45184 KB Output is correct
9 Correct 591 ms 43928 KB Output is correct
10 Correct 583 ms 49436 KB Output is correct
11 Correct 591 ms 45964 KB Output is correct
12 Correct 577 ms 49644 KB Output is correct
13 Correct 530 ms 46016 KB Output is correct
14 Correct 574 ms 49492 KB Output is correct
15 Correct 542 ms 46000 KB Output is correct
16 Correct 599 ms 49564 KB Output is correct
17 Correct 540 ms 46012 KB Output is correct
18 Correct 475 ms 20512 KB Output is correct
19 Runtime error 1872 ms 1048580 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -