oj.uz

Submission #702057

# Submission time Handle Problem Language Result Execution time Memory
702057 2023-02-22T14:44:09 Z ld_minh4354 Crossing (JOI21_crossing) C++14
0 / 100
 73 ms 3924 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],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];
		
		if (s!=e)
		{
			l->lazy=lazy;
			r->lazy=lazy;
		}
		lazy=0;
	}
	
	void update(int S,int E,int V)
	{
//		cout<<s<<" "<<e<<" "<<S<<" "<<E<<"\n"<<flush;
		if (s==S and e==E) lazy=V;
		else
		{
			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;
		}
	}
	
	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];
	
	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";
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:114:15: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  114 |   root->update(l,r,x);
      |   ~~~~~~~~~~~~^~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 3916 KB Output is correct
2 Correct 73 ms 3924 KB Output is correct
3 Correct 71 ms 3796 KB Output is correct
4 Incorrect 60 ms 3904 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 3916 KB Output is correct
2 Correct 73 ms 3924 KB Output is correct
3 Correct 71 ms 3796 KB Output is correct
4 Incorrect 60 ms 3904 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 3916 KB Output is correct
2 Correct 73 ms 3924 KB Output is correct
3 Correct 71 ms 3796 KB Output is correct
4 Incorrect 60 ms 3904 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 3916 KB Output is correct
2 Correct 73 ms 3924 KB Output is correct
3 Correct 71 ms 3796 KB Output is correct
4 Incorrect 60 ms 3904 KB Output isn't correct
5 Halted 0 ms 0 KB -