oj.uz

Submission #832152

# Submission time Handle Problem Language Result Execution time Memory
832152 2023-08-21T04:06:17 Z vjudge1 Crossing (JOI21_crossing) C++17
100 / 100
 356 ms 37792 KB 
#define Magic ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define tsts int t; cin >> t; while(t--)
#include <bits/stdc++.h>
using namespace std;
using lli = long long int;
using ull = unsigned long long int;
using ld = long double;
using str = string;
#define pb push_back
#define pf push_front
#define sz size()
#define bg begin()
#define ers erase
inline void debugMode() {
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif // ONLINE_JUDGE
}
const lli MOD = 1e9 + 7, N = 2e5 * 4 + 100, p = 5;
lli t[N], sm[N], md[N]; //main tree for hash, tree for sums of hashes, tree for modifications
map <str, lli> visited; //visited strings
map <lli, lli> us; //used for hashes
lli pwr[N]; // powers of p
queue <str> que;
str a;
str sa, sb, sc;
lli count_hash(str &s1){
	lli res = 0, p_pow = 1;
	for (lli i = 0 ; i < s1.sz ; i++){
		lli cur;
		if (s1[i] == 'J')
			cur = 1;
		else if (s1[i] == 'O')
			cur = 2;
		else
			cur = 3;
		res+=cur * p_pow;
		res%=MOD;
		p_pow*=p;
		p_pow%=MOD;
	}
	return res;
}
str combine(str &s1, str &s2){
	str res;
	for (lli i = 0 ; i < s1.sz ; i++){
		if (s1[i] == s2[i])
			res.pb(s1[i]);
		else
			res.pb('J' + 'O' + 'I' - s1[i] - s2[i]);
	}
	return res;
}
void bfs(){
	while (!que.empty()){
		str cur = que.front();
		us[count_hash(cur)] = 1;
		que.pop();
		str res = combine(cur, sa);
		if (!visited[res]){
			visited[res] = 1;
			que.push(res);
		}
		res = combine(cur, sb);
		if (!visited[res]){
			visited[res] = 1;
			que.push(res);
		}
		res = combine(cur, sc);
		if (!visited[res]){
			visited[res] = 1;
			que.push(res);
		}
	}
}
void build(lli x, lli tl, lli tr){
	if (tl == tr){
		lli cur;
		if (a[tl] == 'J')
			cur = 1;
		else if (a[tl] == 'O')
			cur = 2;
		else
			cur = 3;
		t[x] = pwr[tl] * cur;
		t[x]%=MOD;
		sm[x] = pwr[tl];
		sm[x]%=MOD; 
	}
	else{
		lli tm = (tl + tr)/2;
		build(x * 2, tl, tm);
		build(x * 2 + 1, tm + 1, tr);
		t[x] = t[2 * x] + t[2 * x + 1];
		t[x]%=MOD;
		sm[x] = sm[2 * x] + sm[2 * x + 1];
		sm[x]%=MOD;
	}
}
void psh(lli x){
	if (md[x] != 0 && 2 * x + 1 < N && t[2 * x] != 0){
		md[2 * x] = md[x];
		md[2 * x + 1] = md[x];
		t[2 * x] = sm[2 * x] * md[2 * x];
		t[2 * x]%=MOD;
		t[2 * x + 1] = sm[2 * x + 1] * md[2 * x + 1];
		t[2 * x + 1]%=MOD;
		md[x] = 0;
	}
}
void update(lli x, lli tl, lli tr, lli l, lli r, lli c){
	if (l > r)
		return ;
	else if (tl == l && tr == r){
		md[x] = c;
		t[x] = sm[x] * c;
		t[x]%=MOD;
	}
	else{
		psh(x);
		lli tm = (tl + tr)/2;
		update(2 * x, tl, tm, l, min(r, tm), c);
		update(2 * x + 1, tm + 1, tr, max(l, tm + 1), r, c);
		t[x] = t[2 * x] + t[2 * x + 1];
		t[x]%=MOD;
	}
}
int main(){
    Magic
    //debugMode();
    lli n, q;
    cin >> n >> sa >> sb >> sc;
   	visited[sa] = 1;
   	visited[sb] = 1;
   	visited[sc] = 1;
   	que.push(sa);
   	que.push(sb);
   	que.push(sc);
   	bfs();
   	pwr[0] = 1;
   	for (lli i = 1 ; i <= N ; i++){
   		pwr[i] = pwr[i - 1] * p;
   		pwr[i]%=MOD;
   	}
   	cin >> q;
   	cin >> a;
   	build(1, 0, a.sz - 1);
   	if (us[t[1]])
   		cout << "Yes\n";
   	else
   		cout << "No\n";
   	while (q--){
   		lli l, r, cur;
   		char c;
   		cin >> l >> r >> c;
   		l--;
   		r--;
   		if (c == 'J')
   			cur = 1;
   		else if (c == 'O')
   			cur = 2;
   		else
   			cur = 3;
   		update(1, 0, a.sz - 1, l, r, cur);
   		if (us[t[1]])
   			cout << "Yes\n";
   		else
   			cout << "No\n";
   	}
}
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⠤⢲⣦⡀⠀⣠⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⣀⣠⠖⠚⠓⠒⠒⠲⠿⣍⣛⣻⣦⣷⢠⣻⣀⠤⠤⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠔⡿⠓⠲⠬⢥⡤⠤⠤⠤⠤⣤⣀⣀⣈⣻⣿⣿⠓⠉⣀⡤⠔⢶⣻⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣤⢤⠞⠁⣼⠀⠀⠀⠀⠀⠀⠰⠶⢌⣽⡶⠟⢏⡁⢈⣉⣭⣷⡯⣝⠒⢦⣄⠙⠷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡾⣵⠿⣳⡟⠉⠉⠿⠀⠀⡀⠀⠀⣀⣀⣢⣾⣿⡚⠓⠒⠒⠒⠻⢿⣟⣧⡀⢠⣢⡻⠙⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡀⢿⣟⣲⢿⣷⢀⣤⣠⣄⣈⢿⣷⣤⣷⣻⡓⠒⠻⠭⢷⡄⠒⠲⢶⣦⣬⣻⣏⢦⡈⢿⣆⠘⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⢖⣩⠷⢎⣙⣿⣿⣼⡼⣿⣟⣽⣻⢯⢿⠞⣌⠙⢳⡕⠀⠙⠲⣶⠤⢄⡠⣄⡈⠛⣿⣿⣧⢳⣌⢻⡆⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠗⠉⢀⣾⠟⠒⡿⣫⡿⡾⢫⢟⡏⠉⢸⡀⠑⢾⡆⢤⣻⣶⣤⣘⣲⣿⣶⡽⠿⣯⠲⣌⣇⢹⣷⣿⣆⠸⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⡼⠀⣿⢣⣧⠋⣸⠀⣰⢀⣿⣆⠀⠰⣄⠙⣧⣨⣿⣿⣿⣯⣿⣦⠘⣷⡌⢻⡄⠿⣆⠟⣆⢇⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⠀⠀⠀⠀⠀⠀⠀⠀⡇⡼⣹⠈⢣⠆⡇⣰⣻⣼⣿⣽⣷⣦⣹⣿⣟⣯⠉⠘⣿⠏⠃⠀⣷⣽⡿⣾⡹⣷⣹⣧⡈⢺⡀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⢾⠟⠉⠀⠀⠀⠀⠀⠀⠀⠀⣷⣱⣽⡀⢸⣆⢳⣿⣇⣷⡿⠖⠿⠷⢦⣙⣆⠩⡗⠀⠀⠀⠀⠀⡯⠿⠳⣟⠻⣽⣄⢧⠈⠳⣷⡀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⣸⡇⡏⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣤⣿⣿⣷⣸⣿⡀⣿⣅⠛⠇⠀⠀⠀⠀⢈⠙⠂⠀⠀⠀⠀⠀⣸⣿⠀⢠⣜⢦⠘⢿⣮⣷⡀⠀⠙⢦⡀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⢯⣇⠙⢄⣀⠀⠀⠀⢀⣀⡠⣴⣾⣫⠵⠛⣿⣻⠿⣷⣹⣾⣷⡠⡀⠀⠀⠀⠻⠦⠀⣀⠔⠀⠀⣴⣿⣸⣧⡀⠳⣝⠳⢴⡙⢞⣏⠢⡀⠀⠹⡄⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⢀⣀⣀⣈⣻⣤⣀⠈⠉⠻⠿⢿⣺⣿⡵⣶⢶⣦⠀⠘⣿⢷⣾⢿⣿⡋⢙⣮⣄⡀⠀⠀⠉⠈⠀⠀⢀⢞⣿⣼⣿⣿⣿⣆⡀⠙⢦⣝⣮⠛⢷⡙⢆⠀⣷⠀⠀⠀⠀
///⠀⠀⠀⢠⡴⢟⣫⠤⠖⠒⠛⢛⣲⣿⣿⣿⠟⠋⢱⣿⣴⣷⣿⣹⢃⣀⣘⠃⢩⢿⣫⣥⣿⠧⢿⣿⣗⡶⣤⣄⣀⣴⣷⣻⣿⣿⠻⠘⣏⠛⢿⣦⣀⠱⢤⣉⡑⠛⠮⢿⣹⠀⠀⠀⠀
///⠀⢠⢖⠵⠊⠁⢀⡤⠖⣲⣿⣿⣟⣻⣿⣋⠀⠀⠈⢿⣿⡿⠟⣵⣿⣿⣿⣷⡏⠈⢿⡿⣷⣤⣼⢿⣿⣿⢶⣯⣭⣵⣾⢿⣿⠿⢦⡀⢹⠀⠈⣏⠉⠉⢻⣶⣯⡑⠦⣄⠈⠳⣄⠀
///⠀⠹⠁⠀⠀⣞⢁⡾⢽⣯⣝⣛⣛⣯⣭⣽⣿⣷⣶⣤⣤⣴⣿⣿⣿⣿⣿⣿⡀⣀⣼⣀⠈⠙⠛⠷⣾⡿⢿⡟⣿⠟⠁⣈⣥⡴⠾⠷⢾⡄⠀⣿⠀⠀⠈⢇⠘⣿⣤⣀⠑⢦⡘⢧⠀
///⠄⠀⠀⠀⠀⠈⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢿⡿⠛⣻⢏⡽⣯⡄⠘⣏⣿⡏⠈⠙⠓⠶⣤⣀⠀⠙⢿⣿⡇⢀⡿⠋⠁⠀⢀⣀⣸⡇⠀⣟⣀⠀⠀⠀⠙⠃⣿⡎⠑⣤⡙⣌⡇
///⠀⠀⠀⠀⠀⠀⠀⠙⢿⣿⣿⣿⣿⣿⣿⣿⡥⣖⡯⠖⢋⣡⡞⣼⣿⠀⠀⢹⣿⣷⠀⠀⣀⡀⠀⠉⠻⣦⠀⢿⣿⡿⠁⣠⡶⠟⠋⠉⠹⣆⣸⣿⣿⠀⣀⡤⣤⡀⣿⠇⠀⢸⠳⡜⡇
///⠀⠀⠀⠀⠀⠀⠀⠀⣈⣿⣿⣿⣿⣿⣿⣏⢿⣗⠒⠊⠉⢸⠁⡿⡏⠀⢀⣿⡿⣁⠤⢶⣿⣽⡆⠀⠀⠘⢷⡈⠉⣡⠾⠋⠀⠀⣠⣆⢠⣿⣿⣿⡟⢀⣷⠒⢺⣧⡏⠀⠀⢸⠀⢹⣹
///⠀⠀⠀⠀⠀⠀⡠⢪⠟⡽⠙⢶⣾⣿⣿⣿⣷⡻⣦⡀⠀⠀⢣⣇⡇⢀⡞⣸⠏⠁⠀⠀⡇⢻⡀⠀⠀⣾⣶⡟⣿⣥⡄⠀⠀⢠⣇⣼⡶⣿⣿⠋⣸⣾⣷⣚⣽⡟⠀⠀⠀⣏⠀⡼⣿
///⠀⠀⠀⠀⢀⠎⡴⣣⣾⠟⣡⠞⢹⡿⣿⢿⣿⣿⣿⣷⣄⠀⠈⠻⡹⣼⠀⣿⡄⠀⠀⠀⠉⠻⣷⡀⠀⠙⠿⠇⣿⠿⠇⠀⠀⢠⡿⠋⢇⢹⣟⢷⠫⣿⣟⡿⠋⠀⠀⣠⣾⢞⡜⠁⡿
///⠀⠀⠀⠀⡼⡼⣵⠏⡏⣰⠃⠀⢾⡇⠈⠻⣿⣮⡉⠹⣿⣧⣄⡀⠙⣇⠀⠸⣿⣄⡀⠀⠀⠀⠈⢉⣧⡴⠀⠠⡄⣀⡤⠤⠴⠋⠁⠀⠈⢻⣿⣾⣤⡿⠋⠀⠀⠀⣉⣽⠿⠋⠀⣰⠃
///⠀⠀⠀⠀⣿⣽⠋⠀⡇⡇⠀⠀⠘⣷⢠⣶⢮⣻⣿⣦⠈⠛⠙⠹⣷⠘⢦⣤⣿⣳⣭⣑⣒⣒⣺⣿⢿⣀⣀⣀⣿⣧⣀⣀⣀⡤⠴⠒⣶⣿⣏⣾⡿⠁⠀⠀⠀⠉⠉⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⢻⡏⠀⠀⢳⣇⠀⠀⠀⠈⠈⣿⣾⣿⣿⣮⣿⣦⠀⠀⢿⣶⡫⣿⣿⣿⣿⣿⡹⣯⣊⠁⠉⠉⠉⠉⢙⣮⣷⣶⡤⣤⣶⣿⣿⣟⣾⢿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠸⣿⣦⡀⠀⠙⠦⠀⠀⢀⣼⠿⣽⣿⣯⣷⣼⡷⢾⣻⣾⣿⠞⢿⢻⡷⠻⣿⣏⡙⢝⣻⡾⡖⠒⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⣎⠣⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠈⠁⠀⠀⠀⠀⣴⣋⣉⣩⣿⣿⢿⣟⣷⣾⣯⡟⢱⡇⠀⠘⣿⠣⡀⣈⣻⣿⣿⣿⣷⣷⣶⣿⣿⣟⠋⡿⣹⣿⣿⣿⣿⢟⣏⠺⠿⠶⠭⠷⠂⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⣿⣿⣿⣿⣿⣿⢹⣮⣾⣿⡿⢋⣶⢸⡇⠀⠀⠈⢷⡑⠈⢻⣟⠛⠛⠿⠋⠙⠓⣭⣿⣹⣵⣿⣿⣿⣿⣿⠈⠻⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⢟⣛⡭⠶⢾⡿⠃⠀⠀⢸⢹⣾⣇⠀⠀⠀⠀⠻⣟⣿⡏⠀⠀⠀⠀⢰⣿⣿⢿⡇⣿⣿⣿⣿⣟⡏⠀⠀⠀⠉⠙⠓⠒⠂⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⡟⠀⠀⠀⢰⣿⢸⣿⢿⡀⠀⠀⠀⠀⢸⣿⣣⠀⠀⠀⢠⣿⡟⣷⣾⣿⢿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣿⠁⠀⠀⠀⠘⡿⡿⢿⣏⣧⠀⠀⠀⢀⣾⣿⠿⠀⢀⣴⣿⣿⢿⡹⡇⣿⠈⣿⣿⡟⣾⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⡇⠀⠀⠀⠀⢳⢧⠈⢿⣿⠀⠀⢀⣼⣿⠕⠁⣠⣾⡿⣻⠏⠀⢹⣹⣿⣆⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⣿⣷⠀⠀⠀⠀⠈⣏⢧⠀⢻⣧⠶⣋⠿⠋⣀⣾⣟⣿⠞⠁⠀⠀⠀⢯⣿⣿⣿⣿⣿⡏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢻⣿⣿⣇⠀⠀⠀⠀⠸⡜⣆⠈⢷⣿⠀⢠⣾⣿⠟⢻⡏⠀⠀⠀⠀⠀⠘⣿⣿⠏⣿⣿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡻⣿⣿⣦⡀⠀⠀⠀⢧⠘⣆⠈⢷⠒⠛⢻⡿⠄⠘⣧⠀⠀⠀⠀⠀⢰⣷⣹⠀⠙⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣷⣝⣿⣿⣷⣄⠀⠀⠈⢇⠸⡄⠈⣇⠀⠀⢻⣆⠀⠘⣇⠀⠀⣠⣾⣽⢹⡟⠀⢰⣷⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢻⣾⢻⠙⢿⣿⡇⠀⠀⠈⢧⢳⠀⢸⡀⠀⠀⢻⣆⠀⢻⡄⢠⣿⣯⣽⣓⣧⣤⠾⢹⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣼⡇⠀⠙⣿⠀⠀⠀⠈⢏⢧⠀⣇⠀⠀⠀⢻⣆⠀⢷⠘⣿⣮⡻⣿⠁⠀⢀⣯⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢿⣿⣧⡀⠀⠀⠀⠀⠀⠀⠘⡾⡄⢸⠀⠀⠀⠈⢻⣆⠈⢷⣷⣾⣟⣻⣶⣿⡿⠛⢿⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣿⣿⣿⣦⣀⠀⠀⠀⠀⠀⢳⣇⠘⡆⠀⠀⠀⠀⠻⣶⢺⡏⢹⡟⠀⠉⠁⠀⠀⠀⢩⣍⠙⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⣟⣿⣿⣿⣧⠀⢀⣤⣤⡸⣸⠀⡇⠀⠀⠀⠀⠀⠙⣿⣷⢡⣿⣶⣄⠀⠀⣄⠀⣦⣍⠙⢳⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⡿⢿⡙⠿⠀⢸⡟⢲⣷⡿⡄⢿⠀⠀⠀⠀⠀⠀⠘⣏⢸⣇⣍⢻⣷⣀⢻⣦⣤⣌⡙⣦⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣯⢷⠀⠀⠸⡇⠀⢿⣧⡇⢸⠀⠀⠀⠀⠀⠀⠀⣼⢸⣿⣯⠀⣿⣿⣷⣝⣿⣻⣿⣼⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢻⣎⣧⠀⠐⣇⠀⠘⣽⣿⡸⡆⠀⠀⠀⠀⠀⠀⠈⠋⠈⠻⣼⣿⢶⢿⣿⣯⡻⣿⣿⣾⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢻⡼⡆⠀⣿⡀⠀⣿⢿⡇⢷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⣾⢧⠈⠙⠿⣮⠟⠉⠙⢦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢿⢻⢠⣿⡇⠀⠹⣄⢳⣜⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⡏⠪⠳⢤⣄⣀⠀⠀⠀⠈⢣⠀⠀⠀⠀⠀⠀⠀⠀⠀
///⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣎⣿⡟⡇⠀⠀⠈⢻⣿⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢳⡄⠀⠀⠀⠙⢧⡀⢀⡄⠈⡇⠀⠀⠀⠀⠀⠀⠀⠀

Compilation message

Main.cpp: In function 'lli count_hash(str&)':
Main.cpp:30:21: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for (lli i = 0 ; i < s1.sz ; i++){
      |                     ^
Main.cpp: In function 'str combine(str&, str&)':
Main.cpp:47:21: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for (lli i = 0 ; i < s1.sz ; i++){
      |                     ^
Main.cpp: In function 'int main()':
Main.cpp:143:13: warning: iteration 800099 invokes undefined behavior [-Waggressive-loop-optimizations]
  143 |      pwr[i] = pwr[i - 1] * p;
      |      ~~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:142:24: note: within this loop
  142 |     for (lli i = 1 ; i <= N ; i++){
      |                      ~~^~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 17868 KB Output is correct
2 Correct 117 ms 18808 KB Output is correct
3 Correct 91 ms 12196 KB Output is correct
4 Correct 138 ms 18736 KB Output is correct
5 Correct 130 ms 18816 KB Output is correct
6 Correct 112 ms 17992 KB Output is correct
7 Correct 113 ms 18380 KB Output is correct
8 Correct 118 ms 19216 KB Output is correct
9 Correct 113 ms 18716 KB Output is correct
10 Correct 155 ms 20296 KB Output is correct
11 Correct 134 ms 19488 KB Output is correct
12 Correct 127 ms 20296 KB Output is correct
13 Correct 155 ms 19500 KB Output is correct
14 Correct 120 ms 20204 KB Output is correct
15 Correct 118 ms 19436 KB Output is correct
16 Correct 179 ms 20236 KB Output is correct
17 Correct 136 ms 19548 KB Output is correct
18 Correct 80 ms 10600 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 17868 KB Output is correct
2 Correct 117 ms 18808 KB Output is correct
3 Correct 91 ms 12196 KB Output is correct
4 Correct 138 ms 18736 KB Output is correct
5 Correct 130 ms 18816 KB Output is correct
6 Correct 112 ms 17992 KB Output is correct
7 Correct 113 ms 18380 KB Output is correct
8 Correct 118 ms 19216 KB Output is correct
9 Correct 113 ms 18716 KB Output is correct
10 Correct 155 ms 20296 KB Output is correct
11 Correct 134 ms 19488 KB Output is correct
12 Correct 127 ms 20296 KB Output is correct
13 Correct 155 ms 19500 KB Output is correct
14 Correct 120 ms 20204 KB Output is correct
15 Correct 118 ms 19436 KB Output is correct
16 Correct 179 ms 20236 KB Output is correct
17 Correct 136 ms 19548 KB Output is correct
18 Correct 80 ms 10600 KB Output is correct
19 Correct 325 ms 33832 KB Output is correct
20 Correct 272 ms 31372 KB Output is correct
21 Correct 262 ms 35212 KB Output is correct
22 Correct 232 ms 32928 KB Output is correct
23 Correct 246 ms 22748 KB Output is correct
24 Correct 181 ms 21596 KB Output is correct
25 Correct 275 ms 36252 KB Output is correct
26 Correct 273 ms 34340 KB Output is correct
27 Correct 309 ms 36632 KB Output is correct
28 Correct 273 ms 34264 KB Output is correct
29 Correct 250 ms 36184 KB Output is correct
30 Correct 197 ms 22824 KB Output is correct
31 Correct 258 ms 36608 KB Output is correct
32 Correct 320 ms 33800 KB Output is correct
33 Correct 159 ms 21408 KB Output is correct
34 Correct 254 ms 34348 KB Output is correct
35 Correct 219 ms 33820 KB Output is correct
36 Correct 185 ms 21548 KB Output is correct
37 Correct 175 ms 21588 KB Output is correct
38 Correct 210 ms 28484 KB Output is correct
39 Correct 155 ms 26528 KB Output is correct
40 Correct 213 ms 27812 KB Output is correct
41 Correct 215 ms 24580 KB Output is correct
42 Correct 50 ms 19624 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 17868 KB Output is correct
2 Correct 117 ms 18808 KB Output is correct
3 Correct 91 ms 12196 KB Output is correct
4 Correct 138 ms 18736 KB Output is correct
5 Correct 130 ms 18816 KB Output is correct
6 Correct 112 ms 17992 KB Output is correct
7 Correct 113 ms 18380 KB Output is correct
8 Correct 118 ms 19216 KB Output is correct
9 Correct 113 ms 18716 KB Output is correct
10 Correct 155 ms 20296 KB Output is correct
11 Correct 134 ms 19488 KB Output is correct
12 Correct 127 ms 20296 KB Output is correct
13 Correct 155 ms 19500 KB Output is correct
14 Correct 120 ms 20204 KB Output is correct
15 Correct 118 ms 19436 KB Output is correct
16 Correct 179 ms 20236 KB Output is correct
17 Correct 136 ms 19548 KB Output is correct
18 Correct 80 ms 10600 KB Output is correct
19 Correct 122 ms 18344 KB Output is correct
20 Correct 90 ms 12232 KB Output is correct
21 Correct 158 ms 19588 KB Output is correct
22 Correct 98 ms 17528 KB Output is correct
23 Correct 117 ms 19772 KB Output is correct
24 Correct 108 ms 18572 KB Output is correct
25 Correct 119 ms 19756 KB Output is correct
26 Correct 126 ms 18252 KB Output is correct
27 Correct 147 ms 19692 KB Output is correct
28 Correct 104 ms 18404 KB Output is correct
29 Correct 121 ms 19012 KB Output is correct
30 Correct 100 ms 17868 KB Output is correct
31 Correct 131 ms 19916 KB Output is correct
32 Correct 118 ms 19784 KB Output is correct
33 Correct 160 ms 19244 KB Output is correct
34 Correct 102 ms 18224 KB Output is correct
35 Correct 135 ms 20300 KB Output is correct
36 Correct 116 ms 19524 KB Output is correct
37 Correct 179 ms 20272 KB Output is correct
38 Correct 145 ms 19480 KB Output is correct
39 Correct 124 ms 20288 KB Output is correct
40 Correct 117 ms 19460 KB Output is correct
41 Correct 149 ms 20396 KB Output is correct
42 Correct 134 ms 19488 KB Output is correct
43 Correct 117 ms 18804 KB Output is correct
44 Correct 114 ms 19248 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 17868 KB Output is correct
2 Correct 117 ms 18808 KB Output is correct
3 Correct 91 ms 12196 KB Output is correct
4 Correct 138 ms 18736 KB Output is correct
5 Correct 130 ms 18816 KB Output is correct
6 Correct 112 ms 17992 KB Output is correct
7 Correct 113 ms 18380 KB Output is correct
8 Correct 118 ms 19216 KB Output is correct
9 Correct 113 ms 18716 KB Output is correct
10 Correct 155 ms 20296 KB Output is correct
11 Correct 134 ms 19488 KB Output is correct
12 Correct 127 ms 20296 KB Output is correct
13 Correct 155 ms 19500 KB Output is correct
14 Correct 120 ms 20204 KB Output is correct
15 Correct 118 ms 19436 KB Output is correct
16 Correct 179 ms 20236 KB Output is correct
17 Correct 136 ms 19548 KB Output is correct
18 Correct 80 ms 10600 KB Output is correct
19 Correct 325 ms 33832 KB Output is correct
20 Correct 272 ms 31372 KB Output is correct
21 Correct 262 ms 35212 KB Output is correct
22 Correct 232 ms 32928 KB Output is correct
23 Correct 246 ms 22748 KB Output is correct
24 Correct 181 ms 21596 KB Output is correct
25 Correct 275 ms 36252 KB Output is correct
26 Correct 273 ms 34340 KB Output is correct
27 Correct 309 ms 36632 KB Output is correct
28 Correct 273 ms 34264 KB Output is correct
29 Correct 250 ms 36184 KB Output is correct
30 Correct 197 ms 22824 KB Output is correct
31 Correct 258 ms 36608 KB Output is correct
32 Correct 320 ms 33800 KB Output is correct
33 Correct 159 ms 21408 KB Output is correct
34 Correct 254 ms 34348 KB Output is correct
35 Correct 219 ms 33820 KB Output is correct
36 Correct 185 ms 21548 KB Output is correct
37 Correct 175 ms 21588 KB Output is correct
38 Correct 210 ms 28484 KB Output is correct
39 Correct 155 ms 26528 KB Output is correct
40 Correct 213 ms 27812 KB Output is correct
41 Correct 215 ms 24580 KB Output is correct
42 Correct 50 ms 19624 KB Output is correct
43 Correct 122 ms 18344 KB Output is correct
44 Correct 90 ms 12232 KB Output is correct
45 Correct 158 ms 19588 KB Output is correct
46 Correct 98 ms 17528 KB Output is correct
47 Correct 117 ms 19772 KB Output is correct
48 Correct 108 ms 18572 KB Output is correct
49 Correct 119 ms 19756 KB Output is correct
50 Correct 126 ms 18252 KB Output is correct
51 Correct 147 ms 19692 KB Output is correct
52 Correct 104 ms 18404 KB Output is correct
53 Correct 121 ms 19012 KB Output is correct
54 Correct 100 ms 17868 KB Output is correct
55 Correct 131 ms 19916 KB Output is correct
56 Correct 118 ms 19784 KB Output is correct
57 Correct 160 ms 19244 KB Output is correct
58 Correct 102 ms 18224 KB Output is correct
59 Correct 135 ms 20300 KB Output is correct
60 Correct 116 ms 19524 KB Output is correct
61 Correct 179 ms 20272 KB Output is correct
62 Correct 145 ms 19480 KB Output is correct
63 Correct 124 ms 20288 KB Output is correct
64 Correct 117 ms 19460 KB Output is correct
65 Correct 149 ms 20396 KB Output is correct
66 Correct 134 ms 19488 KB Output is correct
67 Correct 117 ms 18804 KB Output is correct
68 Correct 114 ms 19248 KB Output is correct
69 Correct 343 ms 33748 KB Output is correct
70 Correct 290 ms 32920 KB Output is correct
71 Correct 166 ms 21620 KB Output is correct
72 Correct 206 ms 21712 KB Output is correct
73 Correct 183 ms 21588 KB Output is correct
74 Correct 229 ms 34748 KB Output is correct
75 Correct 197 ms 22924 KB Output is correct
76 Correct 356 ms 36648 KB Output is correct
77 Correct 257 ms 33500 KB Output is correct
78 Correct 209 ms 21564 KB Output is correct
79 Correct 161 ms 21640 KB Output is correct
80 Correct 273 ms 34884 KB Output is correct
81 Correct 220 ms 22924 KB Output is correct
82 Correct 302 ms 37792 KB Output is correct
83 Correct 259 ms 35136 KB Output is correct
84 Correct 175 ms 21580 KB Output is correct
85 Correct 176 ms 21736 KB Output is correct
86 Correct 241 ms 34068 KB Output is correct
87 Correct 263 ms 35864 KB Output is correct
88 Correct 195 ms 21120 KB Output is correct
89 Correct 335 ms 34796 KB Output is correct
90 Correct 278 ms 36064 KB Output is correct
91 Correct 201 ms 21092 KB Output is correct
92 Correct 222 ms 34920 KB Output is correct
93 Correct 191 ms 21700 KB Output is correct
94 Correct 193 ms 21696 KB Output is correct
95 Correct 179 ms 21580 KB Output is correct
96 Correct 204 ms 28448 KB Output is correct
97 Correct 183 ms 29464 KB Output is correct
98 Correct 241 ms 28852 KB Output is correct
99 Correct 226 ms 26596 KB Output is correct
100 Correct 83 ms 21768 KB Output is correct