Submission #682924

#	Time	Username	Problem	Language	Result	Execution time	Memory
682924		myrcella	Crossing (JOI21_crossing)	C++17	100 / 100	745 ms	90000 KiB

Main

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn = 2e5+10;

int n,m;

int tree[10][maxn*4];
int add[maxn*4];
int cnt[10][maxn*4][3];
int num[maxn];
string s[3];
int comb[9][3] = {{0,0,1},{0,1,0},{1,0,0},{0,2,2},{2,0,2},{2,2,0},{1,1,2},{1,2,1},{2,1,1}};
int val[9][maxn];
string ss;

void init(int c,int cl,int cr) {
	if (cl==cr) {
		rep(i,0,9) tree[i][c] = (num[int(ss[cl])]==val[i][cl]),cnt[i][c][val[i][cl]]=1;
		return;
	}
	int mid=cl+cr>>1;
	init(c<<1,cl,mid);
	init(c<<1|1,mid+1,cr);
	rep(i,0,9) {
		tree[i][c] = tree[i][c<<1] + tree[i][c<<1|1];
		rep(j,0,3) cnt[i][c][j] = cnt[i][c<<1][j] + cnt[i][c<<1|1][j];
	}
	return;
}

void update(int c,int cl,int cr,int l,int r,int x) {
	if (l<=cl and cr<=r) {
		rep(i,0,9) tree[i][c] = cnt[i][c][x];
		add[c] = x;
		return;
	}
	if (add[c]!=-1) {
		int tmp = add[c];
		rep(i,0,9) tree[i][c<<1] = cnt[i][c<<1][tmp], tree[i][c<<1|1] = cnt[i][c<<1|1][tmp];
		add[c<<1] = tmp, add[c<<1|1] = tmp;
		add[c] = -1;
	}
	int mid=cl+cr>>1;
	if (l<=mid) update(c<<1,cl,mid,l,r,x);
	if (r>mid) update(c<<1|1,mid+1,cr,l,r,x);
	rep(i,0,9) tree[i][c] = tree[i][c<<1] + tree[i][c<<1|1];
}

int main() {
//	freopen("input.txt","r",stdin);	
	memset(add,-1,sizeof(add));
	std::ios::sync_with_stdio(false);cin.tie(0);
	num[int('J')]=0,num[int('O')]=1,num[int('I')]=2;
	cin>>n>>s[0]>>s[1]>>s[2];
	rep(i,0,9) {
		rep(k,0,n) {
			int res = 0;
			rep(j,0,3) res += comb[i][j] * num[int(s[j][k])];
			res%=3;
			val[i][k] = res;
//			cout<<val[i][k]<<" ";
		}
//		cout<<endl;
	}
	cin>>m>>ss;
	init(1,0,n-1);
	bool flag= false;
	rep(i,0,9) if (tree[i][1]==n) flag=true;
	if (flag) cout<<"Yes\n";
	else cout<<"No\n";
//	debug(tree[8][1]);
	while (m--) {
		int l,r;char c;
		cin>>l>>r>>c;
		l--,r--;
		update(1,0,n-1,l,r,num[int(c)]);
//		debug(num[int(c)]);
		flag=false;
		rep(i,0,9) if (tree[i][1]==n) {flag=true;break;}
		if (flag) cout<<"Yes\n";
		else cout<<"No\n";
//		debug(tree[8][1]);
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void init(int, int, int)':
Main.cpp:42:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |  int mid=cl+cr>>1;
      |          ~~^~~
Main.cpp: In function 'void update(int, int, int, int, int, int)':
Main.cpp:64:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |  int mid=cl+cr>>1;
      |          ~~^~~

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