Submission #1086643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086643		peacebringer1667	Crossing (JOI21_crossing)	C++17	49 / 100	387 ms	28628 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
#define int long long
using namespace std;
const int base = 137;
const int modu = 1e9 + 7;
const int maxn = 3e5 + 5;

//////////
int pw[maxn],pre[maxn];
char gc(int x){
	if (x == 1) return 'J';
	if (x == 2) return 'O';
	return 'I';
}
int gn(char x){
	if (x == 'J') return 1;
	if (x == 'O') return 2;
	return 3;
}
struct Hash{
	vector <int> pre;
	
	void hashing(const string&s){
		if (!s.size()) return;
		pre.clear();
		pre.push_back((ll)pw[1] * (ll)(s[0] - 96) % modu);
		
		for (int i = 1 ; i < s.size() ; i++)
		  pre.push_back(((ll)pre[i - 1] + (ll)(s[i] - 96) * (ll)pw[i + 1] % modu) % modu);
	    
	    for (int &t : pre)
	      if (t < 0) t += modu;
	}
	
	int Val(){
		if (!pre.size()) return -1;
		return pre.back();
	}
};
void prepare_pw(int n){
	for (int i = 0 ; i <= n ; i++){
	  pw[i] = (!i) ? 1 : (ll)pw[i - 1] * (ll)base % modu;
      pre[i] = (!i) ? 1 : (ll)(pre[i - 1] + pw[i]) % modu;
	}
}
set <int> s;
vector <string> S;
bool contain(int x){
	if (!s.size() || *s.rbegin() < x) return 0;
	
	int y = *s.lower_bound(x);
	return (y == x);
}
string Xor(const string &a,const string &b){
	string c = a;
	
	for (int i = 0 ; i < a.size() ; i++){
	    int x = 6 - gn(a[i]) - gn(b[i]);
	    if (x % 3 == 0) x = 3;
	    else x %= 3;
	    
	    c[i] = gc(x);
	  }
	return c;
}
void insertion(const string &t){
	Hash Hash;
	Hash.hashing(t);
	
	if (contain(Hash.Val())) return;
	s.insert(Hash.Val());
	S.push_back(t);
	
	vector <string> lst;
	
	for (const string &st : S){
		string k = Xor(t,st);
		
		Hash.hashing(k);
		if (!contain(Hash.Val()))
		  lst.push_back(k);
	}
	
	if (lst.size())
	  for (const string &k : lst)
	    insertion(k); 
}
void gen_string(int N){
	for (int id = 1 ; id <= 3 ; id++){
		string t;
		cin >> t;
		insertion(t);
	}
}
////////////

struct segment_tree{
	int seg[4*maxn],lazy[4*maxn];
	
	void downlazy(int v,int l,int r){
		if (!lazy[v]) return;
		
		int sum = (pre[r] - pre[l - 1]) % modu;
		seg[v] = (ll)sum * (ll)lazy[v] % modu;
		
		if (l != r){
			lazy[2*v + 1] = lazy[v];
			lazy[2*v + 2] = lazy[v];
		}
		lazy[v] = 0;
	}
	
	void update(int l,int r,int v,int lx,int rx,int val){
		downlazy(v,l,r);
		
		if (l > rx || r < lx) return;
		if (l >= lx && r <= rx){
			lazy[v] = val;
			downlazy(v,l,r);
			return;
		}
		
		int w = (l + r)/2;
		update(l,w,2*v + 1,lx,rx,val);
		update(w + 1,r,2*v + 2,lx,rx,val);
		seg[v] = (ll)(seg[2*v + 1] + seg[2*v + 2]) % modu;
	}
	
	int calc(){
		if (seg[0] < 0) seg[0] += modu;
		return seg[0];
	}
} seg;

void print_ans(bool x){
	if (x) cout << "Yes";
	else cout << "No";
	cout << "\n";
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	//freopen("crossing.inp","r",stdin);
//	freopen("crossing.out","w",stdout);
	int N;
	cin >> N;
	prepare_pw(N);
	gen_string(N);
	
	int Q;
    string QR;
    cin >> Q >> QR;
    for (int i = 1 ; i <= N ; i++)
      seg.update(1,N,0,i,i,(int)QR[i - 1] - 96);
    
	print_ans(contain(seg.calc()));
    while (Q--){
    	int l,r;char c;
    	cin >> l >> r >> c;
    	seg.update(1,N,0,l,r,c - 96);
    	
    	print_ans(contain(seg.calc()));
	}
    
	return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void Hash::hashing(const string&)':
Main.cpp:35:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for (int i = 1 ; i < s.size() ; i++)
      |                    ~~^~~~~~~~~~
Main.cpp: In function 'std::string Xor(const string&, const string&)':
Main.cpp:64:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for (int i = 0 ; i < a.size() ; i++){
      |                   ~~^~~~~~~~~~

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