Submission #429282

#	Time	Username	Problem	Language	Result	Execution time	Memory
429282		Pyqe	Crossing (JOI21_crossing)	C++14	100 / 100	3492 ms	390048 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long n,a[3][200069],ca[200069];
pair<long long,long long> qq[200069];
bitset<200069> sq;

struct segtree
{
	long long l,r,sm;
	segtree *p[2];
	
	void bd(long long lh,long long rh)
	{
		l=lh;
		r=rh;
		sm=0;
		if(l<r)
		{
			long long ii,md=(l+r)/2;
			
			for(ii=0;ii<2;ii++)
			{
				p[ii]=new segtree;
				p[ii]->bd(!ii?l:md+1,!ii?md:r);
			}
		}
	}
	void bd2(array<segtree*,3> sr)
	{
		long long ii;
		
		for(ii=0;ii<2;ii++)
		{
			if(p[ii]->l==p[ii]->r)
			{
				p[ii]=sr[ca[p[ii]->l]]->p[ii];
			}
			else
			{
				p[ii]->bd2({sr[0]->p[ii],sr[1]->p[ii],sr[2]->p[ii]});
			}
		}
	}
	void rpc(long long lh,long long rh,segtree *sr)
	{
		long long ii;
		segtree *tmp;
		
		for(ii=0;ii<2;ii++)
		{
			if(p[ii]->l>rh||p[ii]->r<lh);
			else if(p[ii]->l>=lh&&p[ii]->r<=rh)
			{
				p[ii]=sr->p[ii];
			}
			else
			{
				tmp=p[ii];
				p[ii]=new segtree;
				*p[ii]=*tmp;
				p[ii]->rpc(lh,rh,sr->p[ii]);
			}
		}
	}
	void bd3(long long x)
	{
		if(l==r)
		{
			sm=ca[l]==x;
		}
		else
		{
			long long ii;
			
			for(ii=0;ii<2;ii++)
			{
				p[ii]->bd3(x);
			}
			sm=p[0]->sm+p[1]->sm;
		}
	}
	void rlx(long long lh,long long rh)
	{
		if(lh+1&&(l>rh||r<lh));
		else if((l>=lh&&r<=rh)||(lh==-1&&l==r));
		else
		{
			long long ii;
			
			for(ii=0;ii<2;ii++)
			{
				p[ii]->rlx(lh,rh);
			}
			sm=p[0]->sm+p[1]->sm;
		}
	}
}
sg[200069];

int main()
{
	long long t,rr,i,j,r,k,l,w;
	char ch;
	
	scanf("%lld",&n);
	n++;
	for(i=0;i<3;i++)
	{
		for(j=1;j<=n-1;j++)
		{
			scanf(" %c",&ch);
			a[i][j]=(ch=='O')+2*(ch=='I');
		}
	}
	scanf("%lld",&t);
	for(i=0;i<3;i++)
	{
		sg[t+1+i].bd(1,n);
	}
	for(i=1;i<=n-1;i++)
	{
		scanf(" %c",&ch);
		ca[i]=(ch=='O')+2*(ch=='I');
	}
	sg[0].bd(1,n);
	sg[0].bd2({&sg[t+1],&sg[t+2],&sg[t+3]});
	qq[0]={-1,-1};
	for(rr=1;rr<=t;rr++)
	{
		scanf("%lld%lld %c",&k,&l,&ch);
		w=(ch=='O')+2*(ch=='I');
		sg[rr]=sg[rr-1];
		sg[rr].rpc(k,l,&sg[t+1+w]);
		qq[rr]={k,l};
	}
	for(i=0;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			k=(4-i-j)%3;
			for(r=1;r<=n;r++)
			{
				ca[r]=(a[0][r]*i+a[1][r]*j+a[2][r]*k)%3;
			}
			for(r=0;r<3;r++)
			{
				sg[t+1+r].bd3(r);
			}
			for(rr=0;rr<=t;rr++)
			{
				k=qq[rr].fr;
				l=qq[rr].sc;
				sg[rr].rlx(k,l);
				sq[rr]=sq[rr]||sg[rr].sm==n;
			}
		}
	}
	for(rr=0;rr<=t;rr++)
	{
		if(sq[rr])
		{
			printf("Yes\n");
		}
		else
		{
			printf("No\n");
		}
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:111:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |  scanf("%lld",&n);
      |  ~~~~~^~~~~~~~~~~
Main.cpp:117:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |    scanf(" %c",&ch);
      |    ~~~~~^~~~~~~~~~~
Main.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |  scanf("%lld",&t);
      |  ~~~~~^~~~~~~~~~~
Main.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |   scanf(" %c",&ch);
      |   ~~~~~^~~~~~~~~~~
Main.cpp:136:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |   scanf("%lld%lld %c",&k,&l,&ch);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 23 / 23
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51