Submission #988972

#	Time	Username	Problem	Language	Result	Execution time	Memory
988972		PenguinsAreCute	Crossing (JOI21_crossing)	C++17	100 / 100	427 ms	11616 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int BASE = 1210;
const int MOD = 998244353;
const int MAXN = 262144;
const int h = 32 - __builtin_clz(MAXN);
int pows[MAXN], ones[MAXN];
int wtf[80];
namespace seg {
	int v[MAXN<<1], lazy[MAXN<<1|1];
	void calc(int x, int k) {
		if(lazy[x]<3) v[x]=(1LL*lazy[x]*ones[k])%MOD;
		else v[x]=(1LL*v[x<<1|1]*pows[k>>1]+v[x<<1])%MOD;
	}
	void app(int x, int u, int k) {
		if(x<MAXN) lazy[x] = u;
		v[x] = (1LL*u*ones[k])%MOD;
	}
	void build(int l, int r) {
		int k = 2;
		for(l+=MAXN,r+=MAXN-1;l>1;k<<=1) {
			l>>=1,r>>=1;
			for(int i=r;i>=l;i--) calc(i,k);
		}
	}
	void push(int l, int r) {
		int k=1<<(h-1), s= h;
		for(l+=MAXN,r+=MAXN-1;s;s--,k>>=1) for(int i=(l>>s);i<=(r>>s);i++) if(lazy[i]<3) {
			app(i<<1,lazy[i],k);
			app(i<<1|1,lazy[i],k);
			lazy[i]=3;
		}
	}
	void init(string s) {
		fill(lazy,lazy+MAXN,3);
		for(int i=0;i<MAXN;i++) v[i+MAXN]=(i<s.size()?wtf[s[i]]:0);
		build(0,MAXN);
	}
	void up(int l, int r, int u) {
		push(l,l+1); push(r-1,r);
		int l0=l, r0=r, k=1;
		for(l+=MAXN,r+=MAXN;l<r;l>>=1,r>>=1,k<<=1) {
			if(l&1) app(l++,u,k);
			if(r&1) app(--r,u,k);
		}
		build(l0,l0+1); build(r0-1,r0);
	}
}
main() {
	pows[0]=1; for(int i=1;i<200005;i++) pows[i]=(1LL*pows[i-1]*BASE)%MOD;
	ones[0]=0; for(int i=1;i<200005;i++) ones[i]=(1LL*ones[i-1]*BASE+1)%MOD;
	wtf[73]=0;wtf[74]=1;wtf[79]=2;
	int n; cin >> n;
	string s1, s2, s3; cin >> s1 >> s2 >> s3;
	vector<int> hsh;
	for(int i=0;i<3;i++) for(int j=0;j<3;j++) {
		int curHsh = 0;
		for(int k=n;k--;) {
			int cur = i*wtf[s1[k]]+j*wtf[s2[k]]+(7-i-j)*wtf[s3[k]];
			cur %= 3;
			curHsh = (1LL * BASE * curHsh + cur) % MOD;
		}
		hsh.push_back(curHsh);
	}
	sort(hsh.begin(),hsh.end());
	int q; string t; cin >> q >> t;
	seg::init(t);
	auto it = lower_bound(hsh.begin(),hsh.end(),seg::v[1]);
	cout<<(it!=hsh.end()&&(*it)==seg::v[1]?"Yes\n":"No\n");
	for(int l,r;q--;) {
		char c; cin >> l >> r >> c;
		seg::up(--l,r,wtf[c]);
		it = lower_bound(hsh.begin(),hsh.end(),seg::v[1]);
		cout<<(it!=hsh.end()&&(*it)==seg::v[1]?"Yes\n":"No\n");
	}
}

Compilation message (stderr)

Main.cpp: In function 'void seg::init(std::string)':
Main.cpp:37:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for(int i=0;i<MAXN;i++) v[i+MAXN]=(i<s.size()?wtf[s[i]]:0);
      |                                      ~^~~~~~~~~
Main.cpp:37:57: warning: array subscript has type 'char' [-Wchar-subscripts]
   37 |   for(int i=0;i<MAXN;i++) v[i+MAXN]=(i<s.size()?wtf[s[i]]:0);
      |                                                         ^
Main.cpp: At global scope:
Main.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main() {
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:60:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   60 |    int cur = i*wtf[s1[k]]+j*wtf[s2[k]]+(7-i-j)*wtf[s3[k]];
      |                         ^
Main.cpp:60:38: warning: array subscript has type 'char' [-Wchar-subscripts]
   60 |    int cur = i*wtf[s1[k]]+j*wtf[s2[k]]+(7-i-j)*wtf[s3[k]];
      |                                      ^
Main.cpp:60:57: warning: array subscript has type 'char' [-Wchar-subscripts]
   60 |    int cur = i*wtf[s1[k]]+j*wtf[s2[k]]+(7-i-j)*wtf[s3[k]];
      |                                                         ^
Main.cpp:73:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   73 |   seg::up(--l,r,wtf[c]);
      |                     ^

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