oj.uz

Submission #537630

# Submission time Handle Problem Language Result Execution time Memory
537630 2022-03-15T10:16:59 Z S2speed Crossing (JOI21_crossing) C++17
49 / 100
 7000 ms 28728 KB 
#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast")

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define all(x) x.begin() , x.end()
#define sze(x) (int)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;

const ll maxn = 2e5 + 16 , maxsq = 450 , inf = 2e16;

set<vector<int>> s;

vector<int> operator+ (vector<int> a , vector<int> b){
	vector<int> res(27);
	for(int i = 0 ; i < 27 ; i++){
		if(a[i] == b[i]){
			res[i] = a[i];
		} else {
			res[i] = 3 - a[i] - b[i];
		}
	}
	return res;
}

vector<int> v[27] , a[27];
int cnt[27][maxsq][3] , Cnt[27][3] , sq[27] , f[maxn] , laz[27][maxsq] , lb[27][maxn] , vs[27];

void relax(int k , int j){
	if(laz[k][j] == -1) return;
	int l = j * sq[k] , r = min(l + sq[k] , vs[k]);
	for(int i = l ; i < r ; i++){
		a[k][i] = laz[k][j];
	}
	laz[k][j] = -1;
	return;
}

void sett(int k , int l , int r , int c){
	int jl = l / sq[k] , jr = r / sq[k];
	if(jl == jr){
		int j = jl;
		relax(k , jl);
		for(int i = l ; i < r ; i++){
			cnt[k][j][a[k][i]]--;
			Cnt[k][a[k][i]]--;
			a[k][i] = c;
			cnt[k][j][a[k][i]]++;
			Cnt[k][a[k][i]]++;
		}
		return;
	}
	relax(k , jl);
	while(l % sq[k]){
		cnt[k][jl][a[k][l]]--;
		Cnt[k][a[k][l]]--;
		a[k][l] = c;
		cnt[k][jl][a[k][l]]++;
		Cnt[k][a[k][l]]++;
		l++;
	}
	relax(k , jr);
	while(r % sq[k]){
		r--;
		cnt[k][jr][a[k][r]]--;
		Cnt[k][a[k][r]]--;
		a[k][r] = c;
		cnt[k][jr][a[k][r]]++;
		Cnt[k][a[k][r]]++;
	}
	for(int j = l / sq[k] , i = l ; j < jr ; j++ , i += sq[k]){
		Cnt[k][0] -= cnt[k][j][0];
		Cnt[k][1] -= cnt[k][j][1];
		Cnt[k][2] -= cnt[k][j][2];
		cnt[k][j][0] = cnt[k][j][1] = cnt[k][j][2] = 0;
		cnt[k][j][c] = min(i + sq[k] , vs[k]) - i;
		Cnt[k][c] += cnt[k][j][c];
		laz[k][j] = c;
	}
	return;
}

bool check(){
	auto it = s.begin() , et = s.end();
	while(it != et){
		vector<int> h = *it; ++it;
		bool res = true;
		for(int k = 0 ; k < 27 && res ; k++){
			if(Cnt[k][0] > 0 && h[k] != 0){
				res = false;
			}
			if(Cnt[k][1] > 0 && h[k] != 1){
				res = false;
			}
			if(Cnt[k][2] > 0 && h[k] != 2){
				res = false;
			}
		}
		if(res) return true;
	}
	return false;
}

/*
5
JJJJJ
JJJJJ
JJJJJ
2
JIIII
2 4 J
3 5 J
*/

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	memset(f , 0 , sizeof(f));
	memset(Cnt , 0 , sizeof(Cnt));
	memset(cnt , 0 , sizeof(cnt));
	memset(laz , -1 , sizeof(laz));
	vector<int> g(27);
	int o = 27;
	for(int t = 0 ; t < 3 ; t++){
		for(int i = 0 ; i < 27 ; i++){
			int h = i % o;
			g[i] = h / (o / 3);
//			cout<<a[i]<<' ';
		}
//		cout<<'\n';
		o /= 3;
		s.insert(g);
	}
	bool hm = true;
	while(hm){
		hm = false;
		auto et = s.end();
		for(auto it = s.begin() ; it != et && !hm ; ++it){
			for(auto jt = it ; jt != et && !hm ; ++jt){
				vector<int> res = (*it) + (*jt);
				if(!s.count(res)){
					s.insert(res);
					hm = true;
				}
			}
		}
	}
//	cout<<"---------------------------\n";
//	auto it = s.begin() , et = s.end();
//	while(it != et){
//		vector<int> res = *it;
//		for(int i = 0 ; i < 27 ; i++){
//			cout<<res[i]<<' ';
//		}
//		cout<<'\n';
//		++it;
//	}
	int n;
	cin>>n;
	o = 9;
	for(int t = 0 ; t < 3 ; t++){
		for(int i = 0 ; i < n ; i++){
			int h;
			char c;
			cin>>c;
			if(c == 'J'){
				h = 0;
			} else if(c == 'O'){
				h = 1;
			} else {
				h = 2;
			}
			f[i] += h * o;
		}
		o /= 3;
	}
	int q;
	cin>>q;
	for(int i = 0 ; i < n ; i++){
		char c;
		int h;
		cin>>c;
		if(c == 'J'){
			h = 0;
		} else if(c == 'O'){
			h = 1;
		} else {
			h = 2;
		}
		a[f[i]].push_back(h);
		v[f[i]].push_back(i);
	}
	for(int k = 0 ; k < 27 ; k++){
		vs[k] = sze(v[k]);
		lb[k][n] = vs[k];
		for(int i = n - 1 ; ~i ; i--){
			lb[k][i] = lb[k][i + 1];
			lb[k][i] -= (f[i] == k);
		}
	}
	for(int k = 0 ; k < 27 ; k++){
		int sz = vs[k];
		sq[k] = (sz == 0 ? 1 : sqrt(sz));
		for(int i = 0 ; i < sz ; i++){
			cnt[k][i / sq[k]][a[k][i]]++;
			Cnt[k][a[k][i]]++;
		}
	}
	cout<<(check() ? "Yes\n" : "No\n");
	for(int i = 0 ; i < q ; i++){
		int l , r , h;
		char c;
		cin>>l>>r>>c; l--;
		if(c == 'J'){
			h = 0;
		} else if(c == 'O'){
			h = 1;
		} else {
			h = 2;
		}
		for(int k = 0 ; k < 27 ; k++){
			if(v[k].empty()) continue;
			int lk = lb[k][l] , rk = lb[k][r];
//			cout<<k<<' '<<lk<<' '<<rk<<' '<<h<<' '<<Cnt[k][0]<<' '<<Cnt[k][1]<<' '<<Cnt[k][2]<<'\n';
			sett(k , lk , rk , h);
		}
		cout<<(check() ? "Yes\n" : "No\n");
	}
	return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 3404 KB Output is correct
2 Correct 135 ms 3568 KB Output is correct
3 Correct 155 ms 3428 KB Output is correct
4 Correct 126 ms 3408 KB Output is correct
5 Correct 120 ms 3492 KB Output is correct
6 Correct 123 ms 3360 KB Output is correct
7 Correct 128 ms 3628 KB Output is correct
8 Correct 130 ms 3496 KB Output is correct
9 Correct 125 ms 3556 KB Output is correct
10 Correct 128 ms 3532 KB Output is correct
11 Correct 122 ms 3532 KB Output is correct
12 Correct 132 ms 3560 KB Output is correct
13 Correct 123 ms 3572 KB Output is correct
14 Correct 120 ms 3484 KB Output is correct
15 Correct 121 ms 3504 KB Output is correct
16 Correct 125 ms 3592 KB Output is correct
17 Correct 124 ms 3484 KB Output is correct
18 Correct 198 ms 3436 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 3404 KB Output is correct
2 Correct 135 ms 3568 KB Output is correct
3 Correct 155 ms 3428 KB Output is correct
4 Correct 126 ms 3408 KB Output is correct
5 Correct 120 ms 3492 KB Output is correct
6 Correct 123 ms 3360 KB Output is correct
7 Correct 128 ms 3628 KB Output is correct
8 Correct 130 ms 3496 KB Output is correct
9 Correct 125 ms 3556 KB Output is correct
10 Correct 128 ms 3532 KB Output is correct
11 Correct 122 ms 3532 KB Output is correct
12 Correct 132 ms 3560 KB Output is correct
13 Correct 123 ms 3572 KB Output is correct
14 Correct 120 ms 3484 KB Output is correct
15 Correct 121 ms 3504 KB Output is correct
16 Correct 125 ms 3592 KB Output is correct
17 Correct 124 ms 3484 KB Output is correct
18 Correct 198 ms 3436 KB Output is correct
19 Correct 1368 ms 28544 KB Output is correct
20 Correct 2686 ms 28648 KB Output is correct
21 Correct 294 ms 26980 KB Output is correct
22 Correct 243 ms 24600 KB Output is correct
23 Correct 174 ms 5520 KB Output is correct
24 Correct 170 ms 5592 KB Output is correct
25 Correct 293 ms 28708 KB Output is correct
26 Correct 274 ms 28428 KB Output is correct
27 Correct 869 ms 28548 KB Output is correct
28 Correct 784 ms 28436 KB Output is correct
29 Correct 846 ms 27876 KB Output is correct
30 Correct 259 ms 5540 KB Output is correct
31 Correct 874 ms 28396 KB Output is correct
32 Correct 668 ms 26540 KB Output is correct
33 Correct 194 ms 5556 KB Output is correct
34 Correct 690 ms 28404 KB Output is correct
35 Correct 270 ms 22332 KB Output is correct
36 Correct 186 ms 5508 KB Output is correct
37 Correct 190 ms 5508 KB Output is correct
38 Correct 1727 ms 28344 KB Output is correct
39 Correct 182 ms 28728 KB Output is correct
40 Correct 333 ms 20456 KB Output is correct
41 Correct 1265 ms 28604 KB Output is correct
42 Correct 1312 ms 28136 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 3404 KB Output is correct
2 Correct 135 ms 3568 KB Output is correct
3 Correct 155 ms 3428 KB Output is correct
4 Correct 126 ms 3408 KB Output is correct
5 Correct 120 ms 3492 KB Output is correct
6 Correct 123 ms 3360 KB Output is correct
7 Correct 128 ms 3628 KB Output is correct
8 Correct 130 ms 3496 KB Output is correct
9 Correct 125 ms 3556 KB Output is correct
10 Correct 128 ms 3532 KB Output is correct
11 Correct 122 ms 3532 KB Output is correct
12 Correct 132 ms 3560 KB Output is correct
13 Correct 123 ms 3572 KB Output is correct
14 Correct 120 ms 3484 KB Output is correct
15 Correct 121 ms 3504 KB Output is correct
16 Correct 125 ms 3592 KB Output is correct
17 Correct 124 ms 3484 KB Output is correct
18 Correct 198 ms 3436 KB Output is correct
19 Correct 265 ms 3512 KB Output is correct
20 Correct 377 ms 3440 KB Output is correct
21 Correct 155 ms 3504 KB Output is correct
22 Correct 135 ms 3376 KB Output is correct
23 Correct 167 ms 3532 KB Output is correct
24 Correct 153 ms 3448 KB Output is correct
25 Correct 157 ms 3524 KB Output is correct
26 Correct 147 ms 3532 KB Output is correct
27 Correct 163 ms 3536 KB Output is correct
28 Correct 142 ms 3388 KB Output is correct
29 Correct 149 ms 3564 KB Output is correct
30 Correct 140 ms 3388 KB Output is correct
31 Correct 211 ms 3560 KB Output is correct
32 Correct 206 ms 3564 KB Output is correct
33 Correct 213 ms 3552 KB Output is correct
34 Correct 213 ms 3348 KB Output is correct
35 Correct 232 ms 3588 KB Output is correct
36 Correct 213 ms 3552 KB Output is correct
37 Correct 239 ms 3576 KB Output is correct
38 Correct 230 ms 3536 KB Output is correct
39 Correct 213 ms 3532 KB Output is correct
40 Correct 205 ms 3512 KB Output is correct
41 Correct 228 ms 3516 KB Output is correct
42 Correct 225 ms 3532 KB Output is correct
43 Correct 216 ms 3448 KB Output is correct
44 Correct 230 ms 3676 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 3404 KB Output is correct
2 Correct 135 ms 3568 KB Output is correct
3 Correct 155 ms 3428 KB Output is correct
4 Correct 126 ms 3408 KB Output is correct
5 Correct 120 ms 3492 KB Output is correct
6 Correct 123 ms 3360 KB Output is correct
7 Correct 128 ms 3628 KB Output is correct
8 Correct 130 ms 3496 KB Output is correct
9 Correct 125 ms 3556 KB Output is correct
10 Correct 128 ms 3532 KB Output is correct
11 Correct 122 ms 3532 KB Output is correct
12 Correct 132 ms 3560 KB Output is correct
13 Correct 123 ms 3572 KB Output is correct
14 Correct 120 ms 3484 KB Output is correct
15 Correct 121 ms 3504 KB Output is correct
16 Correct 125 ms 3592 KB Output is correct
17 Correct 124 ms 3484 KB Output is correct
18 Correct 198 ms 3436 KB Output is correct
19 Correct 1368 ms 28544 KB Output is correct
20 Correct 2686 ms 28648 KB Output is correct
21 Correct 294 ms 26980 KB Output is correct
22 Correct 243 ms 24600 KB Output is correct
23 Correct 174 ms 5520 KB Output is correct
24 Correct 170 ms 5592 KB Output is correct
25 Correct 293 ms 28708 KB Output is correct
26 Correct 274 ms 28428 KB Output is correct
27 Correct 869 ms 28548 KB Output is correct
28 Correct 784 ms 28436 KB Output is correct
29 Correct 846 ms 27876 KB Output is correct
30 Correct 259 ms 5540 KB Output is correct
31 Correct 874 ms 28396 KB Output is correct
32 Correct 668 ms 26540 KB Output is correct
33 Correct 194 ms 5556 KB Output is correct
34 Correct 690 ms 28404 KB Output is correct
35 Correct 270 ms 22332 KB Output is correct
36 Correct 186 ms 5508 KB Output is correct
37 Correct 190 ms 5508 KB Output is correct
38 Correct 1727 ms 28344 KB Output is correct
39 Correct 182 ms 28728 KB Output is correct
40 Correct 333 ms 20456 KB Output is correct
41 Correct 1265 ms 28604 KB Output is correct
42 Correct 1312 ms 28136 KB Output is correct
43 Correct 265 ms 3512 KB Output is correct
44 Correct 377 ms 3440 KB Output is correct
45 Correct 155 ms 3504 KB Output is correct
46 Correct 135 ms 3376 KB Output is correct
47 Correct 167 ms 3532 KB Output is correct
48 Correct 153 ms 3448 KB Output is correct
49 Correct 157 ms 3524 KB Output is correct
50 Correct 147 ms 3532 KB Output is correct
51 Correct 163 ms 3536 KB Output is correct
52 Correct 142 ms 3388 KB Output is correct
53 Correct 149 ms 3564 KB Output is correct
54 Correct 140 ms 3388 KB Output is correct
55 Correct 211 ms 3560 KB Output is correct
56 Correct 206 ms 3564 KB Output is correct
57 Correct 213 ms 3552 KB Output is correct
58 Correct 213 ms 3348 KB Output is correct
59 Correct 232 ms 3588 KB Output is correct
60 Correct 213 ms 3552 KB Output is correct
61 Correct 239 ms 3576 KB Output is correct
62 Correct 230 ms 3536 KB Output is correct
63 Correct 213 ms 3532 KB Output is correct
64 Correct 205 ms 3512 KB Output is correct
65 Correct 228 ms 3516 KB Output is correct
66 Correct 225 ms 3532 KB Output is correct
67 Correct 216 ms 3448 KB Output is correct
68 Correct 230 ms 3676 KB Output is correct
69 Correct 3566 ms 24720 KB Output is correct
70 Execution timed out 7056 ms 28180 KB Time limit exceeded
71 Halted 0 ms 0 KB -