oj.uz

Submission #419651

# Submission time Handle Problem Language Result Execution time Memory
419651 2021-06-07T10:54:19 Z alishahali1382 Crossing (JOI21_crossing) C++14
100 / 100
 1857 ms 47568 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef pair<pii, int> piii;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<" "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": ";for (auto dcba:abcd) cerr<<dcba<<" ";cerr<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) return cout<<x<<"\n", 0;
#define SZ(x) ((int)x.size())

const int inf=1000010000;
const int mod=1000000007;
const int MAXN=300010, TED=5;

int to_int(char ch){
	if (ch=='J') return 0;
	if (ch=='O') return 1;
	return 2;
}

int n, m, q, k, u, v, x, y, t, l, r, ans;
int A[3][MAXN], B[9][MAXN], T0[MAXN];
int Z[27];
char ch;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Solver{
	ll rnd[MAXN], ps[MAXN];
	int Bs[9];
	int seg[MAXN<<2], lazy[MAXN<<2];
	void Start(){
		for (int i=1; i<=n; i++){
			rnd[i]=rng()%mod;
			ps[i]=ps[i-1]+rnd[i];
		}
		for (int j=0; j<9; j++){
			ll sum=0;
			for (int i=1; i<=n; i++) sum+=rnd[i]*B[j][i];
			Bs[j]=sum%mod;
		}
		Build(1, 1, n+1);
	}
	int Build(int id, int tl, int tr){
		lazy[id]=-1;
		if (tr-tl==1) return seg[id]=rnd[tl]*T0[tl]%mod;
		int mid=(tl+tr)>>1;
		return seg[id]=(Build(id<<1, tl, mid)+Build(id<<1 | 1, mid, tr))%mod;
	}
	inline void add_lazy(int id, int tl, int tr, int val){
		// cerr<<"lazy "<<tl<<" "<<tr<<"  "<<val<<"\n";
		lazy[id]=val;
		seg[id]=(ps[tr-1]-ps[tl-1])*val%mod;
	}
	inline void shift(int id, int tl, int tr){
		if (lazy[id]!=-1){
			int mid=(tl+tr)>>1;
			add_lazy(id<<1, tl, mid, lazy[id]);
			add_lazy(id<<1 | 1, mid, tr, lazy[id]);
			lazy[id]=-1;
		}
	}
	void Set(int id, int tl, int tr, int l, int r, int val){
		if (r<=tl || tr<=l) return ;
		if (l<=tl && tr<=r){
			// cerr<<"add_lazy "<<tl<<" "<<tr<<"  "<<val<<"\n";
			add_lazy(id, tl, tr, val);
			return ;
		}
		shift(id, tl, tr);
		int mid=(tl+tr)>>1;
		Set(id<<1, tl, mid, l, r, val);
		Set(id<<1 | 1, mid, tr, l, r, val);
		seg[id]=(seg[id<<1] + seg[id<<1 | 1])%mod;
	}
	bool Solve(){
		for (int i=0; i<9; i++) if (Bs[i]==seg[1]) return 1;
		return 0;
	}
} solver[TED];

bool Solve(){
	for (int i=0; i<TED; i++) if (!solver[i].Solve()) return 0;
	return 1;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	Z[1]=Z[3]=Z[9]=1;
	for (int i=0; i<27; i++){
		for (int x=0; x<27; x++) for (int y=0; y<27; y++) if (Z[x] && Z[y]){
			int a=2*((x/1%3)+(y/1%3))%3;
			int b=2*((x/3%3)+(y/3%3))%3;
			int c=2*((x/9%3)+(y/9%3))%3;
			Z[a+3*b+9*c]=1;
		}
	}
	// for (int i=0; i<27; i++) if (Z[i]) cerr<<i%3<<" "<<i/3%3<<" "<<i/9%3<<"\n";
	cin>>n;
	for (int i=0; i<3; i++){
		for (int j=1; j<=n; j++){
			cin>>ch;
			A[i][j]=to_int(ch);
		}
	}
	for (int z=0; z<27; z++) if (Z[z]){
		int a=(z/1%3), b=(z/3%3), c=(z/9%3);
		for (int i=1; i<=n; i++)
			B[t][i]=(A[0][i]*a + A[1][i]*b + A[2][i]*c)%3;
		t++;
	}
	assert(t==9);
	
	cin>>m;
	for (int i=1; i<=n; i++){
		cin>>ch;
		T0[i]=to_int(ch);
	}
	
	for (int i=0; i<TED; i++) solver[i].Start();
	cout<<(Solve()?"Yes":"No")<<"\n";
	while (m--){
		cin>>l>>r>>ch;
		r++;
		for (int i=0; i<TED; i++) solver[i].Set(1, 1, n+1, l, r, to_int(ch));
		cout<<(Solve()?"Yes":"No")<<"\n";
		// debug(solver.seg[1])
	}

	return 0;
}
/*
4
JOJO
JJOI
OJOO
3
IJOJ
1 4 O
2 2 J
2 4 I

3
JOI
JOI
JOI
2
OJI
1 2 O
1 1 J

*/

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 1116 KB Output is correct
2 Correct 249 ms 1084 KB Output is correct
3 Correct 200 ms 1116 KB Output is correct
4 Correct 158 ms 1132 KB Output is correct
5 Correct 152 ms 1080 KB Output is correct
6 Correct 155 ms 1124 KB Output is correct
7 Correct 159 ms 1100 KB Output is correct
8 Correct 170 ms 1092 KB Output is correct
9 Correct 171 ms 1124 KB Output is correct
10 Correct 171 ms 1148 KB Output is correct
11 Correct 172 ms 1088 KB Output is correct
12 Correct 173 ms 1120 KB Output is correct
13 Correct 169 ms 1108 KB Output is correct
14 Correct 170 ms 1164 KB Output is correct
15 Correct 188 ms 1092 KB Output is correct
16 Correct 165 ms 1048 KB Output is correct
17 Correct 175 ms 1140 KB Output is correct
18 Correct 213 ms 1116 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 1116 KB Output is correct
2 Correct 249 ms 1084 KB Output is correct
3 Correct 200 ms 1116 KB Output is correct
4 Correct 158 ms 1132 KB Output is correct
5 Correct 152 ms 1080 KB Output is correct
6 Correct 155 ms 1124 KB Output is correct
7 Correct 159 ms 1100 KB Output is correct
8 Correct 170 ms 1092 KB Output is correct
9 Correct 171 ms 1124 KB Output is correct
10 Correct 171 ms 1148 KB Output is correct
11 Correct 172 ms 1088 KB Output is correct
12 Correct 173 ms 1120 KB Output is correct
13 Correct 169 ms 1108 KB Output is correct
14 Correct 170 ms 1164 KB Output is correct
15 Correct 188 ms 1092 KB Output is correct
16 Correct 165 ms 1048 KB Output is correct
17 Correct 175 ms 1140 KB Output is correct
18 Correct 213 ms 1116 KB Output is correct
19 Correct 1485 ms 47332 KB Output is correct
20 Correct 1048 ms 47340 KB Output is correct
21 Correct 791 ms 45828 KB Output is correct
22 Correct 844 ms 43368 KB Output is correct
23 Correct 362 ms 3628 KB Output is correct
24 Correct 396 ms 3632 KB Output is correct
25 Correct 922 ms 47396 KB Output is correct
26 Correct 1100 ms 47348 KB Output is correct
27 Correct 1172 ms 47396 KB Output is correct
28 Correct 1218 ms 47324 KB Output is correct
29 Correct 1106 ms 46680 KB Output is correct
30 Correct 470 ms 3664 KB Output is correct
31 Correct 1119 ms 47356 KB Output is correct
32 Correct 1058 ms 45044 KB Output is correct
33 Correct 398 ms 3628 KB Output is correct
34 Correct 1295 ms 47320 KB Output is correct
35 Correct 799 ms 40676 KB Output is correct
36 Correct 387 ms 3608 KB Output is correct
37 Correct 393 ms 3716 KB Output is correct
38 Correct 1054 ms 47348 KB Output is correct
39 Correct 419 ms 47348 KB Output is correct
40 Correct 818 ms 28292 KB Output is correct
41 Correct 1857 ms 47516 KB Output is correct
42 Correct 130 ms 47568 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 1116 KB Output is correct
2 Correct 249 ms 1084 KB Output is correct
3 Correct 200 ms 1116 KB Output is correct
4 Correct 158 ms 1132 KB Output is correct
5 Correct 152 ms 1080 KB Output is correct
6 Correct 155 ms 1124 KB Output is correct
7 Correct 159 ms 1100 KB Output is correct
8 Correct 170 ms 1092 KB Output is correct
9 Correct 171 ms 1124 KB Output is correct
10 Correct 171 ms 1148 KB Output is correct
11 Correct 172 ms 1088 KB Output is correct
12 Correct 173 ms 1120 KB Output is correct
13 Correct 169 ms 1108 KB Output is correct
14 Correct 170 ms 1164 KB Output is correct
15 Correct 188 ms 1092 KB Output is correct
16 Correct 165 ms 1048 KB Output is correct
17 Correct 175 ms 1140 KB Output is correct
18 Correct 213 ms 1116 KB Output is correct
19 Correct 219 ms 1068 KB Output is correct
20 Correct 203 ms 1148 KB Output is correct
21 Correct 226 ms 1164 KB Output is correct
22 Correct 146 ms 1024 KB Output is correct
23 Correct 164 ms 1048 KB Output is correct
24 Correct 173 ms 1040 KB Output is correct
25 Correct 190 ms 1220 KB Output is correct
26 Correct 176 ms 1092 KB Output is correct
27 Correct 185 ms 1144 KB Output is correct
28 Correct 152 ms 1148 KB Output is correct
29 Correct 192 ms 1040 KB Output is correct
30 Correct 155 ms 1020 KB Output is correct
31 Correct 177 ms 1092 KB Output is correct
32 Correct 166 ms 1088 KB Output is correct
33 Correct 171 ms 1156 KB Output is correct
34 Correct 151 ms 1092 KB Output is correct
35 Correct 174 ms 1152 KB Output is correct
36 Correct 172 ms 1136 KB Output is correct
37 Correct 165 ms 1136 KB Output is correct
38 Correct 173 ms 1096 KB Output is correct
39 Correct 175 ms 1092 KB Output is correct
40 Correct 188 ms 1092 KB Output is correct
41 Correct 180 ms 1120 KB Output is correct
42 Correct 175 ms 1128 KB Output is correct
43 Correct 158 ms 1148 KB Output is correct
44 Correct 208 ms 1104 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 1116 KB Output is correct
2 Correct 249 ms 1084 KB Output is correct
3 Correct 200 ms 1116 KB Output is correct
4 Correct 158 ms 1132 KB Output is correct
5 Correct 152 ms 1080 KB Output is correct
6 Correct 155 ms 1124 KB Output is correct
7 Correct 159 ms 1100 KB Output is correct
8 Correct 170 ms 1092 KB Output is correct
9 Correct 171 ms 1124 KB Output is correct
10 Correct 171 ms 1148 KB Output is correct
11 Correct 172 ms 1088 KB Output is correct
12 Correct 173 ms 1120 KB Output is correct
13 Correct 169 ms 1108 KB Output is correct
14 Correct 170 ms 1164 KB Output is correct
15 Correct 188 ms 1092 KB Output is correct
16 Correct 165 ms 1048 KB Output is correct
17 Correct 175 ms 1140 KB Output is correct
18 Correct 213 ms 1116 KB Output is correct
19 Correct 1485 ms 47332 KB Output is correct
20 Correct 1048 ms 47340 KB Output is correct
21 Correct 791 ms 45828 KB Output is correct
22 Correct 844 ms 43368 KB Output is correct
23 Correct 362 ms 3628 KB Output is correct
24 Correct 396 ms 3632 KB Output is correct
25 Correct 922 ms 47396 KB Output is correct
26 Correct 1100 ms 47348 KB Output is correct
27 Correct 1172 ms 47396 KB Output is correct
28 Correct 1218 ms 47324 KB Output is correct
29 Correct 1106 ms 46680 KB Output is correct
30 Correct 470 ms 3664 KB Output is correct
31 Correct 1119 ms 47356 KB Output is correct
32 Correct 1058 ms 45044 KB Output is correct
33 Correct 398 ms 3628 KB Output is correct
34 Correct 1295 ms 47320 KB Output is correct
35 Correct 799 ms 40676 KB Output is correct
36 Correct 387 ms 3608 KB Output is correct
37 Correct 393 ms 3716 KB Output is correct
38 Correct 1054 ms 47348 KB Output is correct
39 Correct 419 ms 47348 KB Output is correct
40 Correct 818 ms 28292 KB Output is correct
41 Correct 1857 ms 47516 KB Output is correct
42 Correct 130 ms 47568 KB Output is correct
43 Correct 219 ms 1068 KB Output is correct
44 Correct 203 ms 1148 KB Output is correct
45 Correct 226 ms 1164 KB Output is correct
46 Correct 146 ms 1024 KB Output is correct
47 Correct 164 ms 1048 KB Output is correct
48 Correct 173 ms 1040 KB Output is correct
49 Correct 190 ms 1220 KB Output is correct
50 Correct 176 ms 1092 KB Output is correct
51 Correct 185 ms 1144 KB Output is correct
52 Correct 152 ms 1148 KB Output is correct
53 Correct 192 ms 1040 KB Output is correct
54 Correct 155 ms 1020 KB Output is correct
55 Correct 177 ms 1092 KB Output is correct
56 Correct 166 ms 1088 KB Output is correct
57 Correct 171 ms 1156 KB Output is correct
58 Correct 151 ms 1092 KB Output is correct
59 Correct 174 ms 1152 KB Output is correct
60 Correct 172 ms 1136 KB Output is correct
61 Correct 165 ms 1136 KB Output is correct
62 Correct 173 ms 1096 KB Output is correct
63 Correct 175 ms 1092 KB Output is correct
64 Correct 188 ms 1092 KB Output is correct
65 Correct 180 ms 1120 KB Output is correct
66 Correct 175 ms 1128 KB Output is correct
67 Correct 158 ms 1148 KB Output is correct
68 Correct 208 ms 1104 KB Output is correct
69 Correct 1400 ms 43152 KB Output is correct
70 Correct 1076 ms 47396 KB Output is correct
71 Correct 346 ms 3692 KB Output is correct
72 Correct 373 ms 3636 KB Output is correct
73 Correct 398 ms 3692 KB Output is correct
74 Correct 808 ms 43016 KB Output is correct
75 Correct 367 ms 3648 KB Output is correct
76 Correct 875 ms 47372 KB Output is correct
77 Correct 865 ms 43040 KB Output is correct
78 Correct 372 ms 3736 KB Output is correct
79 Correct 345 ms 3700 KB Output is correct
80 Correct 798 ms 39968 KB Output is correct
81 Correct 372 ms 3736 KB Output is correct
82 Correct 806 ms 47320 KB Output is correct
83 Correct 869 ms 45828 KB Output is correct
84 Correct 405 ms 3628 KB Output is correct
85 Correct 350 ms 3660 KB Output is correct
86 Correct 1024 ms 41180 KB Output is correct
87 Correct 1071 ms 47348 KB Output is correct
88 Correct 385 ms 3724 KB Output is correct
89 Correct 968 ms 44312 KB Output is correct
90 Correct 1016 ms 47400 KB Output is correct
91 Correct 382 ms 3660 KB Output is correct
92 Correct 716 ms 40860 KB Output is correct
93 Correct 351 ms 3772 KB Output is correct
94 Correct 376 ms 3652 KB Output is correct
95 Correct 411 ms 3648 KB Output is correct
96 Correct 902 ms 47392 KB Output is correct
97 Correct 410 ms 47388 KB Output is correct
98 Correct 699 ms 28484 KB Output is correct
99 Correct 1700 ms 47548 KB Output is correct
100 Correct 127 ms 47528 KB Output is correct