oj.uz

Submission #702115

# Submission time Handle Problem Language Result Execution time Memory
702115 2023-02-23T02:27:20 Z ld_minh4354 Crossing (JOI21_crossing) C++14
100 / 100
 4521 ms 393812 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define debug(x) cout<<#x<<": "<<x<<"\n";

int n,a[200005][12],pre[200005][11][5];

int combine(int x,int y)
{
	int ans=(6-x-y)%3;
	if (ans==0) ans=3;
	return ans;
}

struct node
{
	int s,e,m,val,lazy,id;
	node *l,*r;
	
	node(int S,int E,int ID)
	{
		s=S;e=E;m=(s+e)/2;id=ID;
		val=0;lazy=0;
		
		if (s!=e)
		{
			l=new node(s,m,id);
			r=new node(m+1,e,id);
		}
	}
	
	void propogate()
	{
		if (lazy==0) return;
		
		val=pre[e][id][lazy]-pre[s-1][id][lazy];
//		cout<<s<<" "<<e<<" "<<val<<" "<<lazy<<"\n";
		
		if (s!=e)
		{
			l->lazy=lazy;
			r->lazy=lazy;
		}
		lazy=0;
	}
	
	void update(int S,int E,int V)
	{
		if (s==S and e==E) lazy=V;
		else
		{
			propogate();
			if (E<=m) l->update(S,E,V);
			else if (S>=m+1) r->update(S,E,V);
			else
			{
				l->update(S,m,V);r->update(m+1,E,V);
			}
			
			l->propogate();r->propogate();
			val=l->val+r->val;
		}
//		cout<<s<<" "<<e<<" "<<S<<" "<<E<<" "<<val<<" "<<"\n"<<flush;
	}
	
	int query(int S,int E)
	{
		propogate();
		if (s==S and e==E) return val;
		else if (E<=m) return l->query(S,E);
		else if (S>=m+1) return r->query(S,E);
		else return l->query(S,m)+r->query(m+1,E);
	}
}*root[11];

signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("input.000","r",stdin);
//	freopen("output.000","w",stdout);
//	srand((unsigned)time(NULL));
//	rand()
	
	int i,j,k,l,r,x,q,b[200005];
	string s[5];
	bool ans;
	
	cin>>n>>s[1]>>s[2]>>s[3];
	
	for (i=1;i<n+1;i++) for (j=1;j<4;j++)
	{
		if (s[j][i-1]=='J') a[i][j]=1;
		if (s[j][i-1]=='O') a[i][j]=2;
		if (s[j][i-1]=='I') a[i][j]=3;
	}
	
	for (i=1;i<n+1;i++) a[i][4]=combine(a[i][1],a[i][2]);
	for (i=1;i<n+1;i++) a[i][5]=combine(a[i][3],a[i][2]);
	for (i=1;i<n+1;i++) a[i][6]=combine(a[i][1],a[i][3]);
	for (i=1;i<n+1;i++) a[i][7]=combine(a[i][1],a[i][5]);
	for (i=1;i<n+1;i++) a[i][8]=combine(a[i][2],a[i][6]);
	for (i=1;i<n+1;i++) a[i][9]=combine(a[i][3],a[i][4]);
	
//	for (j=1;j<10;j++)
//	{
//		for (i=1;i<n+1;i++) cout<<a[i][j];
//		cout<<"\n";
//	}
	
	for (i=1;i<10;i++) pre[0][i][1]=pre[0][i][2]=pre[0][i][3]=0;
	for (i=1;i<n+1;i++) for (j=1;j<10;j++) for (k=1;k<4;k++)
	if (a[i][j]==k) pre[i][j][k]=pre[i-1][j][k]+1;else pre[i][j][k]=pre[i-1][j][k];
	
//	for (i=1;i<n+1;i++) cout<<pre[i][1]<<pre[i][2]<<pre[i][3]<<"\n";
	
	cin>>q>>s[1];
	for (i=1;i<n+1;i++)
	{
		if (s[1][i-1]=='J') b[i]=1;
		if (s[1][i-1]=='O') b[i]=2;
		if (s[1][i-1]=='I') b[i]=3;
	}
	
	for (i=1;i<10;i++) root[i]=new node(1,n,i);
	
	ans=false;
	for (i=1;i<n+1;i++) for (j=1;j<10;j++) root[j]->update(i,i,b[i]);
	for (i=1;i<10;i++) if (root[i]->query(1,n) == n) ans=true;
	if (ans) cout<<"Yes\n";else cout<<"No\n";
	
	while(q--)
	{
		cin>>l>>r>>s[1];
		
		if (s[1][0]=='J') x=1;
		if (s[1][0]=='O') x=2;
		if (s[1][0]=='I') x=3;
		
		ans=false;
		for (i=1;i<10;i++)
		{
			root[i]->update(l,r,x);
			if (root[i]->query(1,n) == n) ans=true;
		}
		
		if (ans) cout<<"Yes\n";else cout<<"No\n";
//		for (i=1;i<n+1;i++) cout<<root->query(i,i)<<" ";
//		cout<<"\n";
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:61:31: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |     l->update(S,m,V);r->update(m+1,E,V);
      |                      ~~~~~~~~~^~~~~~~~~
Main.cpp:88:16: note: 'x' was declared here
   88 |  int i,j,k,l,r,x,q,b[200005];
      |                ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 2528 KB Output is correct
2 Correct 297 ms 2664 KB Output is correct
3 Correct 360 ms 2764 KB Output is correct
4 Correct 198 ms 2632 KB Output is correct
5 Correct 200 ms 2688 KB Output is correct
6 Correct 202 ms 2696 KB Output is correct
7 Correct 204 ms 2508 KB Output is correct
8 Correct 220 ms 2684 KB Output is correct
9 Correct 214 ms 2684 KB Output is correct
10 Correct 215 ms 2564 KB Output is correct
11 Correct 216 ms 2656 KB Output is correct
12 Correct 212 ms 2708 KB Output is correct
13 Correct 219 ms 2592 KB Output is correct
14 Correct 207 ms 2572 KB Output is correct
15 Correct 237 ms 2712 KB Output is correct
16 Correct 204 ms 2632 KB Output is correct
17 Correct 213 ms 2652 KB Output is correct
18 Correct 311 ms 2692 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 2528 KB Output is correct
2 Correct 297 ms 2664 KB Output is correct
3 Correct 360 ms 2764 KB Output is correct
4 Correct 198 ms 2632 KB Output is correct
5 Correct 200 ms 2688 KB Output is correct
6 Correct 202 ms 2696 KB Output is correct
7 Correct 204 ms 2508 KB Output is correct
8 Correct 220 ms 2684 KB Output is correct
9 Correct 214 ms 2684 KB Output is correct
10 Correct 215 ms 2564 KB Output is correct
11 Correct 216 ms 2656 KB Output is correct
12 Correct 212 ms 2708 KB Output is correct
13 Correct 219 ms 2592 KB Output is correct
14 Correct 207 ms 2572 KB Output is correct
15 Correct 237 ms 2712 KB Output is correct
16 Correct 204 ms 2632 KB Output is correct
17 Correct 213 ms 2652 KB Output is correct
18 Correct 311 ms 2692 KB Output is correct
19 Correct 4103 ms 390256 KB Output is correct
20 Correct 3671 ms 390344 KB Output is correct
21 Correct 2568 ms 367500 KB Output is correct
22 Correct 2622 ms 329956 KB Output is correct
23 Correct 997 ms 23040 KB Output is correct
24 Correct 971 ms 22700 KB Output is correct
25 Correct 2793 ms 390316 KB Output is correct
26 Correct 2813 ms 390376 KB Output is correct
27 Correct 3472 ms 390328 KB Output is correct
28 Correct 3525 ms 390604 KB Output is correct
29 Correct 3390 ms 379560 KB Output is correct
30 Correct 1118 ms 23296 KB Output is correct
31 Correct 3446 ms 390552 KB Output is correct
32 Correct 3221 ms 356196 KB Output is correct
33 Correct 1016 ms 22632 KB Output is correct
34 Correct 3393 ms 390528 KB Output is correct
35 Correct 2347 ms 291460 KB Output is correct
36 Correct 994 ms 22764 KB Output is correct
37 Correct 1024 ms 22668 KB Output is correct
38 Correct 3073 ms 390420 KB Output is correct
39 Correct 974 ms 390404 KB Output is correct
40 Correct 2615 ms 257152 KB Output is correct
41 Correct 4521 ms 390548 KB Output is correct
42 Correct 606 ms 390484 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 2528 KB Output is correct
2 Correct 297 ms 2664 KB Output is correct
3 Correct 360 ms 2764 KB Output is correct
4 Correct 198 ms 2632 KB Output is correct
5 Correct 200 ms 2688 KB Output is correct
6 Correct 202 ms 2696 KB Output is correct
7 Correct 204 ms 2508 KB Output is correct
8 Correct 220 ms 2684 KB Output is correct
9 Correct 214 ms 2684 KB Output is correct
10 Correct 215 ms 2564 KB Output is correct
11 Correct 216 ms 2656 KB Output is correct
12 Correct 212 ms 2708 KB Output is correct
13 Correct 219 ms 2592 KB Output is correct
14 Correct 207 ms 2572 KB Output is correct
15 Correct 237 ms 2712 KB Output is correct
16 Correct 204 ms 2632 KB Output is correct
17 Correct 213 ms 2652 KB Output is correct
18 Correct 311 ms 2692 KB Output is correct
19 Correct 277 ms 3316 KB Output is correct
20 Correct 369 ms 3276 KB Output is correct
21 Correct 218 ms 3228 KB Output is correct
22 Correct 183 ms 3888 KB Output is correct
23 Correct 206 ms 4272 KB Output is correct
24 Correct 200 ms 4112 KB Output is correct
25 Correct 223 ms 4172 KB Output is correct
26 Correct 191 ms 3968 KB Output is correct
27 Correct 211 ms 4168 KB Output is correct
28 Correct 198 ms 3916 KB Output is correct
29 Correct 217 ms 4164 KB Output is correct
30 Correct 188 ms 3876 KB Output is correct
31 Correct 213 ms 4180 KB Output is correct
32 Correct 202 ms 4068 KB Output is correct
33 Correct 217 ms 4300 KB Output is correct
34 Correct 197 ms 3980 KB Output is correct
35 Correct 211 ms 4128 KB Output is correct
36 Correct 219 ms 4168 KB Output is correct
37 Correct 208 ms 4168 KB Output is correct
38 Correct 224 ms 4124 KB Output is correct
39 Correct 217 ms 4108 KB Output is correct
40 Correct 213 ms 4200 KB Output is correct
41 Correct 210 ms 4168 KB Output is correct
42 Correct 215 ms 4184 KB Output is correct
43 Correct 218 ms 4208 KB Output is correct
44 Correct 233 ms 4252 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 2528 KB Output is correct
2 Correct 297 ms 2664 KB Output is correct
3 Correct 360 ms 2764 KB Output is correct
4 Correct 198 ms 2632 KB Output is correct
5 Correct 200 ms 2688 KB Output is correct
6 Correct 202 ms 2696 KB Output is correct
7 Correct 204 ms 2508 KB Output is correct
8 Correct 220 ms 2684 KB Output is correct
9 Correct 214 ms 2684 KB Output is correct
10 Correct 215 ms 2564 KB Output is correct
11 Correct 216 ms 2656 KB Output is correct
12 Correct 212 ms 2708 KB Output is correct
13 Correct 219 ms 2592 KB Output is correct
14 Correct 207 ms 2572 KB Output is correct
15 Correct 237 ms 2712 KB Output is correct
16 Correct 204 ms 2632 KB Output is correct
17 Correct 213 ms 2652 KB Output is correct
18 Correct 311 ms 2692 KB Output is correct
19 Correct 4103 ms 390256 KB Output is correct
20 Correct 3671 ms 390344 KB Output is correct
21 Correct 2568 ms 367500 KB Output is correct
22 Correct 2622 ms 329956 KB Output is correct
23 Correct 997 ms 23040 KB Output is correct
24 Correct 971 ms 22700 KB Output is correct
25 Correct 2793 ms 390316 KB Output is correct
26 Correct 2813 ms 390376 KB Output is correct
27 Correct 3472 ms 390328 KB Output is correct
28 Correct 3525 ms 390604 KB Output is correct
29 Correct 3390 ms 379560 KB Output is correct
30 Correct 1118 ms 23296 KB Output is correct
31 Correct 3446 ms 390552 KB Output is correct
32 Correct 3221 ms 356196 KB Output is correct
33 Correct 1016 ms 22632 KB Output is correct
34 Correct 3393 ms 390528 KB Output is correct
35 Correct 2347 ms 291460 KB Output is correct
36 Correct 994 ms 22764 KB Output is correct
37 Correct 1024 ms 22668 KB Output is correct
38 Correct 3073 ms 390420 KB Output is correct
39 Correct 974 ms 390404 KB Output is correct
40 Correct 2615 ms 257152 KB Output is correct
41 Correct 4521 ms 390548 KB Output is correct
42 Correct 606 ms 390484 KB Output is correct
43 Correct 277 ms 3316 KB Output is correct
44 Correct 369 ms 3276 KB Output is correct
45 Correct 218 ms 3228 KB Output is correct
46 Correct 183 ms 3888 KB Output is correct
47 Correct 206 ms 4272 KB Output is correct
48 Correct 200 ms 4112 KB Output is correct
49 Correct 223 ms 4172 KB Output is correct
50 Correct 191 ms 3968 KB Output is correct
51 Correct 211 ms 4168 KB Output is correct
52 Correct 198 ms 3916 KB Output is correct
53 Correct 217 ms 4164 KB Output is correct
54 Correct 188 ms 3876 KB Output is correct
55 Correct 213 ms 4180 KB Output is correct
56 Correct 202 ms 4068 KB Output is correct
57 Correct 217 ms 4300 KB Output is correct
58 Correct 197 ms 3980 KB Output is correct
59 Correct 211 ms 4128 KB Output is correct
60 Correct 219 ms 4168 KB Output is correct
61 Correct 208 ms 4168 KB Output is correct
62 Correct 224 ms 4124 KB Output is correct
63 Correct 217 ms 4108 KB Output is correct
64 Correct 213 ms 4200 KB Output is correct
65 Correct 210 ms 4168 KB Output is correct
66 Correct 215 ms 4184 KB Output is correct
67 Correct 218 ms 4208 KB Output is correct
68 Correct 233 ms 4252 KB Output is correct
69 Correct 3600 ms 329652 KB Output is correct
70 Correct 3569 ms 393328 KB Output is correct
71 Correct 1043 ms 24636 KB Output is correct
72 Correct 1055 ms 24940 KB Output is correct
73 Correct 1052 ms 25248 KB Output is correct
74 Correct 2445 ms 328760 KB Output is correct
75 Correct 968 ms 24244 KB Output is correct
76 Correct 2681 ms 393412 KB Output is correct
77 Correct 2562 ms 329284 KB Output is correct
78 Correct 1022 ms 24520 KB Output is correct
79 Correct 960 ms 24780 KB Output is correct
80 Correct 2339 ms 281236 KB Output is correct
81 Correct 912 ms 24400 KB Output is correct
82 Correct 2739 ms 393512 KB Output is correct
83 Correct 2698 ms 370064 KB Output is correct
84 Correct 1002 ms 24452 KB Output is correct
85 Correct 1043 ms 24272 KB Output is correct
86 Correct 3148 ms 300012 KB Output is correct
87 Correct 3506 ms 393692 KB Output is correct
88 Correct 1166 ms 24952 KB Output is correct
89 Correct 2991 ms 347368 KB Output is correct
90 Correct 3317 ms 393532 KB Output is correct
91 Correct 1085 ms 24428 KB Output is correct
92 Correct 2286 ms 295304 KB Output is correct
93 Correct 969 ms 24300 KB Output is correct
94 Correct 1016 ms 24192 KB Output is correct
95 Correct 955 ms 24592 KB Output is correct
96 Correct 2847 ms 393364 KB Output is correct
97 Correct 969 ms 393520 KB Output is correct
98 Correct 2706 ms 259580 KB Output is correct
99 Correct 4284 ms 393812 KB Output is correct
100 Correct 583 ms 392948 KB Output is correct