Submission #702066

#	Time	Username	Problem	Language	Result	Execution time	Memory
702066		ld_minh4354	Crossing (JOI21_crossing)	C++14	26 / 100	379 ms	41012 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],pre[200005][5];

struct node
{
	int s,e,m,val,lazy;
	node *l,*r;
	
	node(int S,int E)
	{
		s=S;e=E;m=(s+e)/2;
		val=0;lazy=0;
		
		if (s!=e)
		{
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void propogate()
	{
		if (lazy==0) return;
		
		val=pre[e][lazy]-pre[s-1][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;

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,l,r,x,q,b[200005];
	string s;
	cin>>n>>s>>s>>s;
	
	for (i=1;i<n+1;i++)
	{
		if (s[i-1]=='J') a[i]=1;
		if (s[i-1]=='O') a[i]=2;
		if (s[i-1]=='I') a[i]=3;
	}
	
	pre[0][1]=pre[0][2]=pre[0][3]=0;
	for (i=1;i<n+1;i++) for (j=1;j<4;j++)
	if (a[i]==j) pre[i][j]=pre[i-1][j]+1;else pre[i][j]=pre[i-1][j];
	
//	for (i=1;i<n+1;i++) cout<<pre[i][1]<<pre[i][2]<<pre[i][3]<<"\n";
	
	cin>>q>>s;
	for (i=1;i<n+1;i++)
	{
		if (s[i-1]=='J') b[i]=1;
		if (s[i-1]=='O') b[i]=2;
		if (s[i-1]=='I') b[i]=3;
	}
	
	root=new node(1,n);
	for (i=1;i<n+1;i++) root->update(i,i,b[i]);
	if (root->query(1,n) == n) cout<<"Yes\n";else cout<<"No\n";
	
	while(q--)
	{
		cin>>l>>r>>s;
		
		if (s[0]=='J') x=1;
		if (s[0]=='O') x=2;
		if (s[0]=='I') x=3;
		
		root->update(l,r,x);
		
		if (root->query(1,n) == n) 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:118:15: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |   root->update(l,r,x);
      |   ~~~~~~~~~~~~^~~~~~~

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