oj.uz

Submission #534029

# Submission time Handle Problem Language Result Execution time Memory
534029 2022-03-07T20:54:28 Z michao Crossing (JOI21_crossing) C++14
100 / 100
 413 ms 20588 KB 
#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAX=1<<18;
const int STALA=2e5;
const int mod=1e9+9;
const int ALFABET=31;
int P[MAX];
set<string>cands;

string func(string a,string b){
	string ans="";
	for (int i=0;i<sz(a);i++){
		char c1=a[i],c2=b[i];
		if (c1==c2)ans+=c1;
		else if (c1=='J' && c2=='O')ans+='I';
		else if (c1=='O' && c2=='J')ans+='I';
		else if (c1=='J' && c2=='I')ans+='O';
		else if (c1=='I' && c2=='J')ans+='O';
		else if (c1=='O' && c2=='I')ans+='J';
		else if (c1=='I' && c2=='O')ans+='J';
	}
	return ans;
}

set<int>Hashes;

int make_hash(string s){
  int Hash=0;
	for (int i=1;i<=sz(s);i++){
		Hash=(Hash+P[i]*(s[i-1]-'A'))%mod;
	}
	return Hash;
}

char lazy[MAX*4];
int S[MAX*4];
int memo[MAX][3];

int conv(char x){
	if (x=='J')return 0;
	if (x=='O')return 1;
	if (x=='I')return 2;
	assert(false);
	return -1;
}

char merguj(char a,char b){
	if (b=='@')return a;
	return b;
}

void push(int u,int lo,int hi){
	if (lazy[u]!='@'){
		char lits=lazy[u];
		int suma=memo[hi-lo+1][conv(lits)];
	  suma=(suma*P[lo-1])%mod;
	  S[u]=suma;
	}
	S[u]%=mod;
	lazy[2*u]=merguj(lazy[2*u],lazy[u]);
	lazy[2*u+1]=merguj(lazy[2*u+1],lazy[u]);
	lazy[u]='@';
}

char lit[3]={'J','O','I'};
void update(int a,int b,int u,int lo,int hi,char lits){
	if (hi<a || lo>b)return;
	push(u,lo,hi);
	if (a<=lo && b>=hi){
		lazy[u]=lits;
		/*
	  int suma=memo[hi-lo+1][conv(lits)];
	  suma=(suma*P[lo-1])%mod;
	  lazy[u]=suma;*/
		return;
	}
	int mid=(lo+hi)>>1;
	update(a,b,2*u,lo,mid,lits);
	update(a,b,2*u+1,mid+1,hi,lits);
	push(2*u,lo,mid);
	push(2*u+1,mid+1,hi);
	S[u]=(S[2*u]+S[2*u+1])%mod;
}

int query(int a,int b,int u,int lo,int hi){
	if (hi<a || lo>b)return 0;
	push(u,lo,hi);
	if (a<=lo && b>=hi)return S[u];
	int mid=(lo+hi)>>1;
	int L=query(a,b,2*u,lo,mid);
	int R=query(a,b,2*u+1,mid+1,hi);
	return (L+R)%mod;
}

int n;

void check(){
	int x=S[1];
	assert(S[1]==query(1,n,1,1,MAX));
	//cout<<"TERAZ "<<x<<"\n";
	if (Hashes.find(x)!=Hashes.end())cout<<"Yes\n";
	else cout<<"No\n";
}


int32_t main(){
  BOOST;
	fill(lazy,lazy+4*MAX,'@');
  P[0]=1;
  for (int i=1;i<=MAX-1;i++)P[i]=(P[i-1]*ALFABET)%mod;
  
  for (int i=0;i<3;i++){
		int akt=0;
		for (int j=1;j<=MAX-1;j++){
			akt+=P[j]*(lit[i]-'A');
			akt%=mod;
			memo[j][i]=akt;
		}
  }	
  cin>>n;
  string s[3];
  cin>>s[0]>>s[1]>>s[2];
  cands.ins(s[0]);
  cands.ins(s[1]);
  cands.ins(s[2]);
  cands.ins(func(s[0],s[1]));
  cands.ins(func(s[1],s[2]));
  cands.ins(func(s[0],s[2]));
  cands.ins(func(s[0],func(s[1],s[2])));
  cands.ins(func(s[1],func(s[0],s[2])));
  cands.ins(func(s[2],func(s[0],s[1])));
  
  //for (auto it:cands)cout<<it<<" "<<make_hash(it)<<"\n";
  
  for (auto it:cands){
		Hashes.ins((make_hash(it))%mod);
  }
  int q;
  cin>>q;
  string t;
  cin>>t;
  for (int i=1;i<=sz(t);i++){
		update(i,i,1,1,MAX,t[i-1]);
  }
  check();
  for (int z=0;z<q;z++){
		int l,r;
		char c;
		cin>>l>>r>>c;
		update(l,r,1,1,MAX,c);
		check();
  }
  return 0; 
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 11472 KB Output is correct
2 Correct 175 ms 11656 KB Output is correct
3 Correct 193 ms 11844 KB Output is correct
4 Correct 165 ms 11556 KB Output is correct
5 Correct 165 ms 11616 KB Output is correct
6 Correct 152 ms 11572 KB Output is correct
7 Correct 173 ms 11592 KB Output is correct
8 Correct 169 ms 11608 KB Output is correct
9 Correct 169 ms 11696 KB Output is correct
10 Correct 173 ms 11684 KB Output is correct
11 Correct 172 ms 11668 KB Output is correct
12 Correct 166 ms 11604 KB Output is correct
13 Correct 175 ms 11800 KB Output is correct
14 Correct 166 ms 11688 KB Output is correct
15 Correct 168 ms 11716 KB Output is correct
16 Correct 171 ms 11736 KB Output is correct
17 Correct 168 ms 11592 KB Output is correct
18 Correct 176 ms 11612 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 11472 KB Output is correct
2 Correct 175 ms 11656 KB Output is correct
3 Correct 193 ms 11844 KB Output is correct
4 Correct 165 ms 11556 KB Output is correct
5 Correct 165 ms 11616 KB Output is correct
6 Correct 152 ms 11572 KB Output is correct
7 Correct 173 ms 11592 KB Output is correct
8 Correct 169 ms 11608 KB Output is correct
9 Correct 169 ms 11696 KB Output is correct
10 Correct 173 ms 11684 KB Output is correct
11 Correct 172 ms 11668 KB Output is correct
12 Correct 166 ms 11604 KB Output is correct
13 Correct 175 ms 11800 KB Output is correct
14 Correct 166 ms 11688 KB Output is correct
15 Correct 168 ms 11716 KB Output is correct
16 Correct 171 ms 11736 KB Output is correct
17 Correct 168 ms 11592 KB Output is correct
18 Correct 176 ms 11612 KB Output is correct
19 Correct 363 ms 18236 KB Output is correct
20 Correct 358 ms 18108 KB Output is correct
21 Correct 302 ms 17740 KB Output is correct
22 Correct 275 ms 17368 KB Output is correct
23 Correct 211 ms 12820 KB Output is correct
24 Correct 193 ms 12780 KB Output is correct
25 Correct 290 ms 18208 KB Output is correct
26 Correct 289 ms 18160 KB Output is correct
27 Correct 334 ms 18140 KB Output is correct
28 Correct 334 ms 18108 KB Output is correct
29 Correct 339 ms 17908 KB Output is correct
30 Correct 204 ms 12740 KB Output is correct
31 Correct 325 ms 18176 KB Output is correct
32 Correct 330 ms 17884 KB Output is correct
33 Correct 207 ms 12752 KB Output is correct
34 Correct 320 ms 18116 KB Output is correct
35 Correct 264 ms 16644 KB Output is correct
36 Correct 193 ms 12716 KB Output is correct
37 Correct 191 ms 12744 KB Output is correct
38 Correct 344 ms 18128 KB Output is correct
39 Correct 252 ms 18232 KB Output is correct
40 Correct 224 ms 16516 KB Output is correct
41 Correct 364 ms 18300 KB Output is correct
42 Correct 215 ms 17584 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 11472 KB Output is correct
2 Correct 175 ms 11656 KB Output is correct
3 Correct 193 ms 11844 KB Output is correct
4 Correct 165 ms 11556 KB Output is correct
5 Correct 165 ms 11616 KB Output is correct
6 Correct 152 ms 11572 KB Output is correct
7 Correct 173 ms 11592 KB Output is correct
8 Correct 169 ms 11608 KB Output is correct
9 Correct 169 ms 11696 KB Output is correct
10 Correct 173 ms 11684 KB Output is correct
11 Correct 172 ms 11668 KB Output is correct
12 Correct 166 ms 11604 KB Output is correct
13 Correct 175 ms 11800 KB Output is correct
14 Correct 166 ms 11688 KB Output is correct
15 Correct 168 ms 11716 KB Output is correct
16 Correct 171 ms 11736 KB Output is correct
17 Correct 168 ms 11592 KB Output is correct
18 Correct 176 ms 11612 KB Output is correct
19 Correct 187 ms 11636 KB Output is correct
20 Correct 184 ms 11536 KB Output is correct
21 Correct 187 ms 11696 KB Output is correct
22 Correct 167 ms 11588 KB Output is correct
23 Correct 170 ms 11720 KB Output is correct
24 Correct 167 ms 11564 KB Output is correct
25 Correct 173 ms 11628 KB Output is correct
26 Correct 175 ms 11588 KB Output is correct
27 Correct 168 ms 11672 KB Output is correct
28 Correct 160 ms 11472 KB Output is correct
29 Correct 168 ms 11672 KB Output is correct
30 Correct 163 ms 11468 KB Output is correct
31 Correct 176 ms 11720 KB Output is correct
32 Correct 179 ms 11680 KB Output is correct
33 Correct 171 ms 11652 KB Output is correct
34 Correct 164 ms 11464 KB Output is correct
35 Correct 168 ms 11676 KB Output is correct
36 Correct 171 ms 11620 KB Output is correct
37 Correct 171 ms 11648 KB Output is correct
38 Correct 179 ms 11680 KB Output is correct
39 Correct 168 ms 11704 KB Output is correct
40 Correct 170 ms 11868 KB Output is correct
41 Correct 168 ms 11648 KB Output is correct
42 Correct 177 ms 11716 KB Output is correct
43 Correct 169 ms 11608 KB Output is correct
44 Correct 173 ms 11716 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 11472 KB Output is correct
2 Correct 175 ms 11656 KB Output is correct
3 Correct 193 ms 11844 KB Output is correct
4 Correct 165 ms 11556 KB Output is correct
5 Correct 165 ms 11616 KB Output is correct
6 Correct 152 ms 11572 KB Output is correct
7 Correct 173 ms 11592 KB Output is correct
8 Correct 169 ms 11608 KB Output is correct
9 Correct 169 ms 11696 KB Output is correct
10 Correct 173 ms 11684 KB Output is correct
11 Correct 172 ms 11668 KB Output is correct
12 Correct 166 ms 11604 KB Output is correct
13 Correct 175 ms 11800 KB Output is correct
14 Correct 166 ms 11688 KB Output is correct
15 Correct 168 ms 11716 KB Output is correct
16 Correct 171 ms 11736 KB Output is correct
17 Correct 168 ms 11592 KB Output is correct
18 Correct 176 ms 11612 KB Output is correct
19 Correct 363 ms 18236 KB Output is correct
20 Correct 358 ms 18108 KB Output is correct
21 Correct 302 ms 17740 KB Output is correct
22 Correct 275 ms 17368 KB Output is correct
23 Correct 211 ms 12820 KB Output is correct
24 Correct 193 ms 12780 KB Output is correct
25 Correct 290 ms 18208 KB Output is correct
26 Correct 289 ms 18160 KB Output is correct
27 Correct 334 ms 18140 KB Output is correct
28 Correct 334 ms 18108 KB Output is correct
29 Correct 339 ms 17908 KB Output is correct
30 Correct 204 ms 12740 KB Output is correct
31 Correct 325 ms 18176 KB Output is correct
32 Correct 330 ms 17884 KB Output is correct
33 Correct 207 ms 12752 KB Output is correct
34 Correct 320 ms 18116 KB Output is correct
35 Correct 264 ms 16644 KB Output is correct
36 Correct 193 ms 12716 KB Output is correct
37 Correct 191 ms 12744 KB Output is correct
38 Correct 344 ms 18128 KB Output is correct
39 Correct 252 ms 18232 KB Output is correct
40 Correct 224 ms 16516 KB Output is correct
41 Correct 364 ms 18300 KB Output is correct
42 Correct 215 ms 17584 KB Output is correct
43 Correct 187 ms 11636 KB Output is correct
44 Correct 184 ms 11536 KB Output is correct
45 Correct 187 ms 11696 KB Output is correct
46 Correct 167 ms 11588 KB Output is correct
47 Correct 170 ms 11720 KB Output is correct
48 Correct 167 ms 11564 KB Output is correct
49 Correct 173 ms 11628 KB Output is correct
50 Correct 175 ms 11588 KB Output is correct
51 Correct 168 ms 11672 KB Output is correct
52 Correct 160 ms 11472 KB Output is correct
53 Correct 168 ms 11672 KB Output is correct
54 Correct 163 ms 11468 KB Output is correct
55 Correct 176 ms 11720 KB Output is correct
56 Correct 179 ms 11680 KB Output is correct
57 Correct 171 ms 11652 KB Output is correct
58 Correct 164 ms 11464 KB Output is correct
59 Correct 168 ms 11676 KB Output is correct
60 Correct 171 ms 11620 KB Output is correct
61 Correct 171 ms 11648 KB Output is correct
62 Correct 179 ms 11680 KB Output is correct
63 Correct 168 ms 11704 KB Output is correct
64 Correct 170 ms 11868 KB Output is correct
65 Correct 168 ms 11648 KB Output is correct
66 Correct 177 ms 11716 KB Output is correct
67 Correct 169 ms 11608 KB Output is correct
68 Correct 173 ms 11716 KB Output is correct
69 Correct 343 ms 18808 KB Output is correct
70 Correct 398 ms 20512 KB Output is correct
71 Correct 190 ms 12832 KB Output is correct
72 Correct 191 ms 12848 KB Output is correct
73 Correct 195 ms 12732 KB Output is correct
74 Correct 278 ms 17472 KB Output is correct
75 Correct 205 ms 12884 KB Output is correct
76 Correct 301 ms 18744 KB Output is correct
77 Correct 305 ms 17700 KB Output is correct
78 Correct 188 ms 12716 KB Output is correct
79 Correct 207 ms 12868 KB Output is correct
80 Correct 298 ms 18040 KB Output is correct
81 Correct 214 ms 12868 KB Output is correct
82 Correct 313 ms 20312 KB Output is correct
83 Correct 324 ms 19824 KB Output is correct
84 Correct 192 ms 12868 KB Output is correct
85 Correct 194 ms 12868 KB Output is correct
86 Correct 317 ms 18476 KB Output is correct
87 Correct 322 ms 20352 KB Output is correct
88 Correct 206 ms 12816 KB Output is correct
89 Correct 299 ms 19280 KB Output is correct
90 Correct 336 ms 20392 KB Output is correct
91 Correct 199 ms 12820 KB Output is correct
92 Correct 297 ms 18276 KB Output is correct
93 Correct 195 ms 12868 KB Output is correct
94 Correct 188 ms 12880 KB Output is correct
95 Correct 196 ms 12800 KB Output is correct
96 Correct 328 ms 17980 KB Output is correct
97 Correct 277 ms 20548 KB Output is correct
98 Correct 236 ms 17856 KB Output is correct
99 Correct 413 ms 20588 KB Output is correct
100 Correct 237 ms 19840 KB Output is correct