oj.uz

Submission #440547

# Submission time Handle Problem Language Result Execution time Memory
440547 2021-07-02T12:31:26 Z ogibogi2004 Crossing (JOI21_crossing) C++14
100 / 100
 2384 ms 27372 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+6;
vector<string>p;
int n;
string cross(string s1,string s2)
{
	string ret="";
	for(int i=0;i<s1.size();i++)
	{
		if(s1[i]==s2[i])ret+=s1[i];
		else ret+=char('J'+'O'+'I'-s1[i]-s2[i]);
	}
	return ret;
}
bool tree[9][3*MAXN];
char lazy[9][3*MAXN];
char tree1[9][3*MAXN];
bool pushed[9][3*MAXN];
void push_lazy(int l,int r,int idx)
{
	for(int j=0;j<9;j++)
	{
		if(pushed[j][idx])continue;
		if(tree1[j][idx]==lazy[j][idx])tree[j][idx]=1;
		else tree[j][idx]=0;
		pushed[j][idx]=1;
		if(l!=r)
		{
			pushed[j][idx*2]=0;
			pushed[j][idx*2+1]=0;
			lazy[j][idx*2]=lazy[j][idx];
			lazy[j][idx*2+1]=lazy[j][idx];
		}
	}
}
void build(int l,int r,int idx)
{
	if(l==r)
	{
		for(int j=0;j<9;j++)tree1[j][idx]=p[j][l];
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,idx*2);
	build(mid+1,r,idx*2+1);
	for(int j=0;j<9;j++)
	{
		if(tree1[j][idx*2]==tree1[j][idx*2+1])
		{
			tree1[j][idx]=tree1[j][idx*2];
		}
		else tree1[j][idx]='o';
	}
}
void update(int l,int r,int idx,int ql,int qr,char val)
{
	//cout<<l<<" "<<r<<" "<<idx<<endl;
	push_lazy(l,r,idx);
	if(l>qr)return;
	if(r<ql)return;
	if(l>=ql&&r<=qr)
	{
		for(int j=0;j<9;j++)
		{
			lazy[j][idx]=val;
			pushed[j][idx]=0;
		}
		push_lazy(l,r,idx);
		return;
	}
	int mid=(l+r)/2;
	update(l,mid,idx*2,ql,qr,val);
	update(mid+1,r,idx*2+1,ql,qr,val);
	for(int j=0;j<9;j++)
	{
		tree[j][idx]=(tree[j][idx*2]&tree[j][idx*2+1]);
	}
}
void print(int l,int r,int idx,int idx1)
{
	cout<<l<<" "<<r<<" "<<tree[idx1][idx]<<endl;
	if(l==r)return;
	int mid=(l+r)/2;
	print(l,mid,idx*2,idx1);
	print(mid+1,r,idx*2+1,idx1);
}
int main()
{
	memset(pushed,1,sizeof(pushed));
	cin>>n;
	string s;
	cin>>s;
	s=" "+s;
	p.push_back(s);
	cin>>s;
	s=" "+s;
	p.push_back(s);
	cin>>s;
	s=" "+s;
	p.push_back(s);
	p.push_back(cross(p[0],p[1]));
	p.push_back(cross(p[2],p[1]));
	p.push_back(cross(p[0],p[2]));
	p.push_back(cross(cross(p[0],p[2]),p[1]));
	p.push_back(cross(cross(p[0],p[1]),p[2]));
	p.push_back(cross(cross(p[2],p[1]),p[0]));
	/*cout<<"p:\n";
	for(int i=0;i<p.size();i++)cout<<p[i]<<endl;
	cout<<"\n^\n";*/
	build(1,n,1);
	int q;
	cin>>q;
	cin>>s;
	s=" "+s;
	for(int i=1;i<s.size();i++)
	{
		update(1,n,1,i,i,s[i]);
	}
	bool ans=0;
	ans=0;
	for(int j=0;j<9;j++)
	{
		ans=(ans|tree[j][1]);
	}
	if(ans)cout<<"Yes\n";
	else cout<<"No\n";
	for(int i=0;i<q;i++)
	{
		int l,r;
		char c;
		cin>>l>>r;cin>>c;
		update(1,n,1,l,r,c);
		ans=0;
		for(int j=0;j<9;j++)
		{
			ans=(ans|tree[j][1]);
		}
		/*for(int j=0;j<9;j++)
		{
			cout<<j<<":\n";
			print(1,n,1,j);
		}*/
		if(ans)cout<<"Yes\n";
		else cout<<"No\n";
	}
return 0;
}

Compilation message

Main.cpp: In function 'std::string cross(std::string, std::string)':
Main.cpp:9:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |  for(int i=0;i<s1.size();i++)
      |              ~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:116:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |  for(int i=1;i<s.size();i++)
      |              ~^~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 575 ms 7592 KB Output is correct
2 Correct 648 ms 7860 KB Output is correct
3 Correct 716 ms 7796 KB Output is correct
4 Correct 537 ms 7748 KB Output is correct
5 Correct 542 ms 7708 KB Output is correct
6 Correct 545 ms 7716 KB Output is correct
7 Correct 546 ms 7860 KB Output is correct
8 Correct 572 ms 7800 KB Output is correct
9 Correct 553 ms 7748 KB Output is correct
10 Correct 568 ms 7876 KB Output is correct
11 Correct 562 ms 7816 KB Output is correct
12 Correct 596 ms 7852 KB Output is correct
13 Correct 562 ms 7892 KB Output is correct
14 Correct 577 ms 7800 KB Output is correct
15 Correct 576 ms 7748 KB Output is correct
16 Correct 558 ms 7784 KB Output is correct
17 Correct 567 ms 7748 KB Output is correct
18 Correct 625 ms 7720 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 575 ms 7592 KB Output is correct
2 Correct 648 ms 7860 KB Output is correct
3 Correct 716 ms 7796 KB Output is correct
4 Correct 537 ms 7748 KB Output is correct
5 Correct 542 ms 7708 KB Output is correct
6 Correct 545 ms 7716 KB Output is correct
7 Correct 546 ms 7860 KB Output is correct
8 Correct 572 ms 7800 KB Output is correct
9 Correct 553 ms 7748 KB Output is correct
10 Correct 568 ms 7876 KB Output is correct
11 Correct 562 ms 7816 KB Output is correct
12 Correct 596 ms 7852 KB Output is correct
13 Correct 562 ms 7892 KB Output is correct
14 Correct 577 ms 7800 KB Output is correct
15 Correct 576 ms 7748 KB Output is correct
16 Correct 558 ms 7784 KB Output is correct
17 Correct 567 ms 7748 KB Output is correct
18 Correct 625 ms 7720 KB Output is correct
19 Correct 2109 ms 27252 KB Output is correct
20 Correct 1932 ms 26328 KB Output is correct
21 Correct 1328 ms 26780 KB Output is correct
22 Correct 1353 ms 26124 KB Output is correct
23 Correct 759 ms 9712 KB Output is correct
24 Correct 799 ms 9640 KB Output is correct
25 Correct 1448 ms 27108 KB Output is correct
26 Correct 1554 ms 27112 KB Output is correct
27 Correct 1827 ms 27104 KB Output is correct
28 Correct 1740 ms 27088 KB Output is correct
29 Correct 1609 ms 26856 KB Output is correct
30 Correct 832 ms 9688 KB Output is correct
31 Correct 1726 ms 27064 KB Output is correct
32 Correct 1569 ms 26432 KB Output is correct
33 Correct 817 ms 9680 KB Output is correct
34 Correct 1762 ms 27080 KB Output is correct
35 Correct 1233 ms 25640 KB Output is correct
36 Correct 769 ms 9792 KB Output is correct
37 Correct 805 ms 9776 KB Output is correct
38 Correct 1745 ms 26168 KB Output is correct
39 Correct 1111 ms 25948 KB Output is correct
40 Correct 1239 ms 18612 KB Output is correct
41 Correct 2384 ms 27372 KB Output is correct
42 Correct 733 ms 25412 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 575 ms 7592 KB Output is correct
2 Correct 648 ms 7860 KB Output is correct
3 Correct 716 ms 7796 KB Output is correct
4 Correct 537 ms 7748 KB Output is correct
5 Correct 542 ms 7708 KB Output is correct
6 Correct 545 ms 7716 KB Output is correct
7 Correct 546 ms 7860 KB Output is correct
8 Correct 572 ms 7800 KB Output is correct
9 Correct 553 ms 7748 KB Output is correct
10 Correct 568 ms 7876 KB Output is correct
11 Correct 562 ms 7816 KB Output is correct
12 Correct 596 ms 7852 KB Output is correct
13 Correct 562 ms 7892 KB Output is correct
14 Correct 577 ms 7800 KB Output is correct
15 Correct 576 ms 7748 KB Output is correct
16 Correct 558 ms 7784 KB Output is correct
17 Correct 567 ms 7748 KB Output is correct
18 Correct 625 ms 7720 KB Output is correct
19 Correct 598 ms 7676 KB Output is correct
20 Correct 671 ms 7652 KB Output is correct
21 Correct 589 ms 7844 KB Output is correct
22 Correct 501 ms 7660 KB Output is correct
23 Correct 581 ms 7976 KB Output is correct
24 Correct 571 ms 7752 KB Output is correct
25 Correct 573 ms 7796 KB Output is correct
26 Correct 534 ms 7640 KB Output is correct
27 Correct 566 ms 7828 KB Output is correct
28 Correct 543 ms 7540 KB Output is correct
29 Correct 568 ms 7744 KB Output is correct
30 Correct 524 ms 7660 KB Output is correct
31 Correct 567 ms 7856 KB Output is correct
32 Correct 557 ms 7768 KB Output is correct
33 Correct 567 ms 7816 KB Output is correct
34 Correct 523 ms 7928 KB Output is correct
35 Correct 567 ms 7748 KB Output is correct
36 Correct 561 ms 7872 KB Output is correct
37 Correct 554 ms 7876 KB Output is correct
38 Correct 610 ms 7928 KB Output is correct
39 Correct 593 ms 7896 KB Output is correct
40 Correct 561 ms 7764 KB Output is correct
41 Correct 571 ms 7748 KB Output is correct
42 Correct 570 ms 7840 KB Output is correct
43 Correct 539 ms 7812 KB Output is correct
44 Correct 568 ms 7856 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 575 ms 7592 KB Output is correct
2 Correct 648 ms 7860 KB Output is correct
3 Correct 716 ms 7796 KB Output is correct
4 Correct 537 ms 7748 KB Output is correct
5 Correct 542 ms 7708 KB Output is correct
6 Correct 545 ms 7716 KB Output is correct
7 Correct 546 ms 7860 KB Output is correct
8 Correct 572 ms 7800 KB Output is correct
9 Correct 553 ms 7748 KB Output is correct
10 Correct 568 ms 7876 KB Output is correct
11 Correct 562 ms 7816 KB Output is correct
12 Correct 596 ms 7852 KB Output is correct
13 Correct 562 ms 7892 KB Output is correct
14 Correct 577 ms 7800 KB Output is correct
15 Correct 576 ms 7748 KB Output is correct
16 Correct 558 ms 7784 KB Output is correct
17 Correct 567 ms 7748 KB Output is correct
18 Correct 625 ms 7720 KB Output is correct
19 Correct 2109 ms 27252 KB Output is correct
20 Correct 1932 ms 26328 KB Output is correct
21 Correct 1328 ms 26780 KB Output is correct
22 Correct 1353 ms 26124 KB Output is correct
23 Correct 759 ms 9712 KB Output is correct
24 Correct 799 ms 9640 KB Output is correct
25 Correct 1448 ms 27108 KB Output is correct
26 Correct 1554 ms 27112 KB Output is correct
27 Correct 1827 ms 27104 KB Output is correct
28 Correct 1740 ms 27088 KB Output is correct
29 Correct 1609 ms 26856 KB Output is correct
30 Correct 832 ms 9688 KB Output is correct
31 Correct 1726 ms 27064 KB Output is correct
32 Correct 1569 ms 26432 KB Output is correct
33 Correct 817 ms 9680 KB Output is correct
34 Correct 1762 ms 27080 KB Output is correct
35 Correct 1233 ms 25640 KB Output is correct
36 Correct 769 ms 9792 KB Output is correct
37 Correct 805 ms 9776 KB Output is correct
38 Correct 1745 ms 26168 KB Output is correct
39 Correct 1111 ms 25948 KB Output is correct
40 Correct 1239 ms 18612 KB Output is correct
41 Correct 2384 ms 27372 KB Output is correct
42 Correct 733 ms 25412 KB Output is correct
43 Correct 598 ms 7676 KB Output is correct
44 Correct 671 ms 7652 KB Output is correct
45 Correct 589 ms 7844 KB Output is correct
46 Correct 501 ms 7660 KB Output is correct
47 Correct 581 ms 7976 KB Output is correct
48 Correct 571 ms 7752 KB Output is correct
49 Correct 573 ms 7796 KB Output is correct
50 Correct 534 ms 7640 KB Output is correct
51 Correct 566 ms 7828 KB Output is correct
52 Correct 543 ms 7540 KB Output is correct
53 Correct 568 ms 7744 KB Output is correct
54 Correct 524 ms 7660 KB Output is correct
55 Correct 567 ms 7856 KB Output is correct
56 Correct 557 ms 7768 KB Output is correct
57 Correct 567 ms 7816 KB Output is correct
58 Correct 523 ms 7928 KB Output is correct
59 Correct 567 ms 7748 KB Output is correct
60 Correct 561 ms 7872 KB Output is correct
61 Correct 554 ms 7876 KB Output is correct
62 Correct 610 ms 7928 KB Output is correct
63 Correct 593 ms 7896 KB Output is correct
64 Correct 561 ms 7764 KB Output is correct
65 Correct 571 ms 7748 KB Output is correct
66 Correct 570 ms 7840 KB Output is correct
67 Correct 539 ms 7812 KB Output is correct
68 Correct 568 ms 7856 KB Output is correct
69 Correct 1829 ms 25980 KB Output is correct
70 Correct 1875 ms 26352 KB Output is correct
71 Correct 771 ms 9704 KB Output is correct
72 Correct 774 ms 9724 KB Output is correct
73 Correct 782 ms 9604 KB Output is correct
74 Correct 1308 ms 25996 KB Output is correct
75 Correct 770 ms 9712 KB Output is correct
76 Correct 1464 ms 27152 KB Output is correct
77 Correct 1395 ms 26128 KB Output is correct
78 Correct 788 ms 9744 KB Output is correct
79 Correct 786 ms 9684 KB Output is correct
80 Correct 1282 ms 25612 KB Output is correct
81 Correct 809 ms 9692 KB Output is correct
82 Correct 1517 ms 27104 KB Output is correct
83 Correct 1557 ms 26876 KB Output is correct
84 Correct 804 ms 9592 KB Output is correct
85 Correct 784 ms 9784 KB Output is correct
86 Correct 1556 ms 25796 KB Output is correct
87 Correct 1790 ms 27208 KB Output is correct
88 Correct 894 ms 9824 KB Output is correct
89 Correct 1591 ms 26404 KB Output is correct
90 Correct 1689 ms 27072 KB Output is correct
91 Correct 819 ms 9676 KB Output is correct
92 Correct 1253 ms 25684 KB Output is correct
93 Correct 786 ms 9696 KB Output is correct
94 Correct 769 ms 9792 KB Output is correct
95 Correct 764 ms 9592 KB Output is correct
96 Correct 1665 ms 26140 KB Output is correct
97 Correct 1038 ms 26028 KB Output is correct
98 Correct 1267 ms 18892 KB Output is correct
99 Correct 2323 ms 27340 KB Output is correct
100 Correct 739 ms 25412 KB Output is correct