oj.uz

Submission #702066

# Submission time Handle Problem Language Result Execution time Memory
702066 2023-02-22T15:24:26 Z ld_minh4354 Crossing (JOI21_crossing) C++14
26 / 100
 379 ms 41012 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];
//		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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2380 KB Output is correct
2 Correct 70 ms 2468 KB Output is correct
3 Correct 69 ms 2476 KB Output is correct
4 Correct 58 ms 2456 KB Output is correct
5 Correct 57 ms 3960 KB Output is correct
6 Correct 57 ms 3892 KB Output is correct
7 Correct 59 ms 3916 KB Output is correct
8 Correct 63 ms 3972 KB Output is correct
9 Correct 61 ms 3968 KB Output is correct
10 Correct 60 ms 3968 KB Output is correct
11 Correct 61 ms 3992 KB Output is correct
12 Correct 60 ms 3916 KB Output is correct
13 Correct 61 ms 3916 KB Output is correct
14 Correct 60 ms 3960 KB Output is correct
15 Correct 63 ms 3944 KB Output is correct
16 Correct 60 ms 3916 KB Output is correct
17 Correct 61 ms 3964 KB Output is correct
18 Correct 66 ms 3836 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2380 KB Output is correct
2 Correct 70 ms 2468 KB Output is correct
3 Correct 69 ms 2476 KB Output is correct
4 Correct 58 ms 2456 KB Output is correct
5 Correct 57 ms 3960 KB Output is correct
6 Correct 57 ms 3892 KB Output is correct
7 Correct 59 ms 3916 KB Output is correct
8 Correct 63 ms 3972 KB Output is correct
9 Correct 61 ms 3968 KB Output is correct
10 Correct 60 ms 3968 KB Output is correct
11 Correct 61 ms 3992 KB Output is correct
12 Correct 60 ms 3916 KB Output is correct
13 Correct 61 ms 3916 KB Output is correct
14 Correct 60 ms 3960 KB Output is correct
15 Correct 63 ms 3944 KB Output is correct
16 Correct 60 ms 3916 KB Output is correct
17 Correct 61 ms 3964 KB Output is correct
18 Correct 66 ms 3836 KB Output is correct
19 Correct 347 ms 40808 KB Output is correct
20 Correct 283 ms 40732 KB Output is correct
21 Correct 227 ms 38528 KB Output is correct
22 Correct 223 ms 34960 KB Output is correct
23 Correct 110 ms 6616 KB Output is correct
24 Correct 101 ms 6492 KB Output is correct
25 Correct 241 ms 40768 KB Output is correct
26 Correct 265 ms 40736 KB Output is correct
27 Correct 288 ms 40728 KB Output is correct
28 Correct 297 ms 40808 KB Output is correct
29 Correct 263 ms 39648 KB Output is correct
30 Correct 106 ms 6504 KB Output is correct
31 Correct 285 ms 40748 KB Output is correct
32 Correct 268 ms 37508 KB Output is correct
33 Correct 98 ms 6448 KB Output is correct
34 Correct 312 ms 40928 KB Output is correct
35 Correct 235 ms 31460 KB Output is correct
36 Correct 95 ms 6468 KB Output is correct
37 Correct 106 ms 6596 KB Output is correct
38 Correct 233 ms 40492 KB Output is correct
39 Correct 133 ms 40736 KB Output is correct
40 Correct 251 ms 28508 KB Output is correct
41 Correct 379 ms 41012 KB Output is correct
42 Correct 89 ms 40212 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2380 KB Output is correct
2 Correct 70 ms 2468 KB Output is correct
3 Correct 69 ms 2476 KB Output is correct
4 Correct 58 ms 2456 KB Output is correct
5 Correct 57 ms 3960 KB Output is correct
6 Correct 57 ms 3892 KB Output is correct
7 Correct 59 ms 3916 KB Output is correct
8 Correct 63 ms 3972 KB Output is correct
9 Correct 61 ms 3968 KB Output is correct
10 Correct 60 ms 3968 KB Output is correct
11 Correct 61 ms 3992 KB Output is correct
12 Correct 60 ms 3916 KB Output is correct
13 Correct 61 ms 3916 KB Output is correct
14 Correct 60 ms 3960 KB Output is correct
15 Correct 63 ms 3944 KB Output is correct
16 Correct 60 ms 3916 KB Output is correct
17 Correct 61 ms 3964 KB Output is correct
18 Correct 66 ms 3836 KB Output is correct
19 Correct 71 ms 3840 KB Output is correct
20 Correct 76 ms 3896 KB Output is correct
21 Incorrect 61 ms 3916 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2380 KB Output is correct
2 Correct 70 ms 2468 KB Output is correct
3 Correct 69 ms 2476 KB Output is correct
4 Correct 58 ms 2456 KB Output is correct
5 Correct 57 ms 3960 KB Output is correct
6 Correct 57 ms 3892 KB Output is correct
7 Correct 59 ms 3916 KB Output is correct
8 Correct 63 ms 3972 KB Output is correct
9 Correct 61 ms 3968 KB Output is correct
10 Correct 60 ms 3968 KB Output is correct
11 Correct 61 ms 3992 KB Output is correct
12 Correct 60 ms 3916 KB Output is correct
13 Correct 61 ms 3916 KB Output is correct
14 Correct 60 ms 3960 KB Output is correct
15 Correct 63 ms 3944 KB Output is correct
16 Correct 60 ms 3916 KB Output is correct
17 Correct 61 ms 3964 KB Output is correct
18 Correct 66 ms 3836 KB Output is correct
19 Correct 347 ms 40808 KB Output is correct
20 Correct 283 ms 40732 KB Output is correct
21 Correct 227 ms 38528 KB Output is correct
22 Correct 223 ms 34960 KB Output is correct
23 Correct 110 ms 6616 KB Output is correct
24 Correct 101 ms 6492 KB Output is correct
25 Correct 241 ms 40768 KB Output is correct
26 Correct 265 ms 40736 KB Output is correct
27 Correct 288 ms 40728 KB Output is correct
28 Correct 297 ms 40808 KB Output is correct
29 Correct 263 ms 39648 KB Output is correct
30 Correct 106 ms 6504 KB Output is correct
31 Correct 285 ms 40748 KB Output is correct
32 Correct 268 ms 37508 KB Output is correct
33 Correct 98 ms 6448 KB Output is correct
34 Correct 312 ms 40928 KB Output is correct
35 Correct 235 ms 31460 KB Output is correct
36 Correct 95 ms 6468 KB Output is correct
37 Correct 106 ms 6596 KB Output is correct
38 Correct 233 ms 40492 KB Output is correct
39 Correct 133 ms 40736 KB Output is correct
40 Correct 251 ms 28508 KB Output is correct
41 Correct 379 ms 41012 KB Output is correct
42 Correct 89 ms 40212 KB Output is correct
43 Correct 71 ms 3840 KB Output is correct
44 Correct 76 ms 3896 KB Output is correct
45 Incorrect 61 ms 3916 KB Output isn't correct
46 Halted 0 ms 0 KB -