Submission #702115

#	Time	Username	Problem	Language	Result	Execution time	Memory
702115		ld_minh4354	Crossing (JOI21_crossing)	C++14	100 / 100	4521 ms	393812 KiB

Main

#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 (stderr)

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 / 3
• Subtask 2: 23 / 23
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51