oj.uz

Submission #436411

# Submission time Handle Problem Language Result Execution time Memory
436411 2021-06-24T13:24:46 Z Blagojce Crossing (JOI21_crossing) C++11
26 / 100
 1333 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(int a, int b, int &m){
	string ns;
	ns.resize(n);
	
	fr(i, 0, n){
		if(s[a][i] == s[b][i]){
			ns[i] = s[a][i];
		}
		else{
			fr(j, 0, 3){
				if(alp[j] != s[a][i] && alp[j] != s[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(i, 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 565 ms 39568 KB Output is correct
2 Correct 541 ms 44244 KB Output is correct
3 Correct 585 ms 25504 KB Output is correct
4 Correct 519 ms 44140 KB Output is correct
5 Correct 515 ms 44512 KB Output is correct
6 Correct 546 ms 42192 KB Output is correct
7 Correct 590 ms 40592 KB Output is correct
8 Correct 520 ms 45088 KB Output is correct
9 Correct 575 ms 43924 KB Output is correct
10 Correct 599 ms 49540 KB Output is correct
11 Correct 587 ms 45988 KB Output is correct
12 Correct 590 ms 49428 KB Output is correct
13 Correct 562 ms 45928 KB Output is correct
14 Correct 605 ms 49544 KB Output is correct
15 Correct 533 ms 45956 KB Output is correct
16 Correct 615 ms 49540 KB Output is correct
17 Correct 625 ms 46048 KB Output is correct
18 Correct 495 ms 20512 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 39568 KB Output is correct
2 Correct 541 ms 44244 KB Output is correct
3 Correct 585 ms 25504 KB Output is correct
4 Correct 519 ms 44140 KB Output is correct
5 Correct 515 ms 44512 KB Output is correct
6 Correct 546 ms 42192 KB Output is correct
7 Correct 590 ms 40592 KB Output is correct
8 Correct 520 ms 45088 KB Output is correct
9 Correct 575 ms 43924 KB Output is correct
10 Correct 599 ms 49540 KB Output is correct
11 Correct 587 ms 45988 KB Output is correct
12 Correct 590 ms 49428 KB Output is correct
13 Correct 562 ms 45928 KB Output is correct
14 Correct 605 ms 49544 KB Output is correct
15 Correct 533 ms 45956 KB Output is correct
16 Correct 615 ms 49540 KB Output is correct
17 Correct 625 ms 46048 KB Output is correct
18 Correct 495 ms 20512 KB Output is correct
19 Runtime error 1333 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 565 ms 39568 KB Output is correct
2 Correct 541 ms 44244 KB Output is correct
3 Correct 585 ms 25504 KB Output is correct
4 Correct 519 ms 44140 KB Output is correct
5 Correct 515 ms 44512 KB Output is correct
6 Correct 546 ms 42192 KB Output is correct
7 Correct 590 ms 40592 KB Output is correct
8 Correct 520 ms 45088 KB Output is correct
9 Correct 575 ms 43924 KB Output is correct
10 Correct 599 ms 49540 KB Output is correct
11 Correct 587 ms 45988 KB Output is correct
12 Correct 590 ms 49428 KB Output is correct
13 Correct 562 ms 45928 KB Output is correct
14 Correct 605 ms 49544 KB Output is correct
15 Correct 533 ms 45956 KB Output is correct
16 Correct 615 ms 49540 KB Output is correct
17 Correct 625 ms 46048 KB Output is correct
18 Correct 495 ms 20512 KB Output is correct
19 Correct 546 ms 42896 KB Output is correct
20 Correct 526 ms 25608 KB Output is correct
21 Correct 661 ms 48736 KB Output is correct
22 Correct 508 ms 36468 KB Output is correct
23 Correct 743 ms 48868 KB Output is correct
24 Correct 594 ms 43512 KB Output is correct
25 Correct 681 ms 48836 KB Output is correct
26 Correct 545 ms 37880 KB Output is correct
27 Correct 645 ms 48804 KB Output is correct
28 Correct 530 ms 43524 KB Output is correct
29 Correct 619 ms 44764 KB Output is correct
30 Correct 501 ms 37156 KB Output is correct
31 Correct 621 ms 48792 KB Output is correct
32 Correct 694 ms 48944 KB Output is correct
33 Correct 649 ms 45300 KB Output is correct
34 Correct 482 ms 40260 KB Output is correct
35 Correct 601 ms 49472 KB Output is correct
36 Correct 642 ms 46044 KB Output is correct
37 Correct 688 ms 49484 KB Output is correct
38 Correct 586 ms 46052 KB Output is correct
39 Correct 677 ms 49608 KB Output is correct
40 Correct 636 ms 46000 KB Output is correct
41 Correct 608 ms 49524 KB Output is correct
42 Correct 577 ms 46000 KB Output is correct
43 Correct 545 ms 41620 KB Output is correct
44 Correct 612 ms 45264 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 39568 KB Output is correct
2 Correct 541 ms 44244 KB Output is correct
3 Correct 585 ms 25504 KB Output is correct
4 Correct 519 ms 44140 KB Output is correct
5 Correct 515 ms 44512 KB Output is correct
6 Correct 546 ms 42192 KB Output is correct
7 Correct 590 ms 40592 KB Output is correct
8 Correct 520 ms 45088 KB Output is correct
9 Correct 575 ms 43924 KB Output is correct
10 Correct 599 ms 49540 KB Output is correct
11 Correct 587 ms 45988 KB Output is correct
12 Correct 590 ms 49428 KB Output is correct
13 Correct 562 ms 45928 KB Output is correct
14 Correct 605 ms 49544 KB Output is correct
15 Correct 533 ms 45956 KB Output is correct
16 Correct 615 ms 49540 KB Output is correct
17 Correct 625 ms 46048 KB Output is correct
18 Correct 495 ms 20512 KB Output is correct
19 Runtime error 1333 ms 1048580 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -