Submission #445054

#	Time	Username	Problem	Language	Result	Execution time	Memory
445054		arnold518	Crossing (JOI21_crossing)	C++17	100 / 100	356 ms	23136 KiB

Main

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const ll MOD = 1e9+9;

int N, Q;
char S[MAXN+10];
vector<int> A[3], B;
vector<ll> V;
ll ppow[MAXN+10];

vector<int> read()
{
	scanf(" %s", S);
	vector<int> ans;
	for(int i=0; i<N; i++)
	{
		if(S[i]=='J') ans.push_back(0);
		else if(S[i]=='O') ans.push_back(1);
		else if(S[i]=='I') ans.push_back(2);
	}
	return ans;
}

ll gethash(vector<int> V)
{
	ll ret=0;
	for(int i=0; i<N; i++)
	{
		ret=(ret+(V[i]+1)*ppow[i])%MOD;
	}
	return ret;
}

struct SEG
{
	ll tree[MAXN*4+10], lazy[MAXN*4+10], sum[MAXN*4+10];

	void init(int node, int tl, int tr, vector<int> &V)
	{
		if(tl==tr)
		{
			tree[node]=(V[tl]+1)*ppow[tl]%MOD;
			sum[node]=ppow[tl]%MOD;
			lazy[node]=0;
			return;
		}
		int mid=tl+tr>>1;
		init(node*2, tl, mid, V);
		init(node*2+1, mid+1, tr, V);
		tree[node]=(tree[node*2]+tree[node*2+1])%MOD;
		sum[node]=(sum[node*2]+sum[node*2+1])%MOD;
		lazy[node]=0;
	}

	void busy(int node, int tl, int tr)
	{
		if(lazy[node]==0) return;
		tree[node]=lazy[node]*sum[node]%MOD;		
		if(tl==tr)
		{
			lazy[node]=0;
			return;
		}
		lazy[node*2]=lazy[node];
		lazy[node*2+1]=lazy[node];
		lazy[node]=0;
	}

	void update(int node, int tl, int tr, int l, int r, int k)
	{
		busy(node, tl, tr);
		if(l<=tl && tr<=r)
		{
			lazy[node]=k;
			busy(node, tl, tr);
			return;
		}
		if(r<tl || tr<l)
		{
			return;
		}
		int mid=tl+tr>>1;
		update(node*2, tl, mid, l, r, k);
		update(node*2+1, mid+1, tr, l, r, k);
		tree[node]=(tree[node*2]+tree[node*2+1])%MOD;
	}

	ll query()
	{
		busy(1, 0, N-1);
		return tree[1];
	}
}seg;

bool solve()
{
	ll t=seg.query();
	for(auto it : V)
	{	
		if(t==it) return true;
	}
	return false;
}

int main()
{
	scanf("%d", &N);

	ppow[0]=1;
	for(int i=1; i<=N; i++)
	{
		ppow[i]=ppow[i-1]*4%MOD;
	}
	for(int i=0; i<3; i++)
	{
		A[i]=read();
	}

	for(int i=0; i<3; i++) for(int j=0; j<3; j++)
	{
		int k=7-i-j;
		k%=3;

		vector<int> now(N);
		for(int p=0; p<N; p++)
		{
			now[p]+=A[0][p]*i;
			now[p]+=A[1][p]*j;
			now[p]+=A[2][p]*k;
			now[p]%=3;
		}
		V.push_back(gethash(now));
	}

	scanf("%d", &Q);
	B=read();

	seg.init(1, 0, N-1, B);
	printf("%s\n", solve() ? "Yes" : "No");
	while(Q--)
	{
		int l, r, k; char c;
		scanf("%d%d %c", &l, &r, &c);
		l--, r--;
		if(c=='J') k=1;
		else if(c=='O') k=2;
		else if(c=='I') k=3;
		seg.update(1, 0, N-1, l, r, k);
		printf("%s\n", solve() ? "Yes" : "No");
	}
}

Compilation message (stderr)

Main.cpp: In member function 'void SEG::init(int, int, int, std::vector<int>&)':
Main.cpp:53:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In member function 'void SEG::update(int, int, int, int, int, int)':
Main.cpp:88:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In function 'std::vector<int> read()':
Main.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  scanf(" %s", S);
      |  ~~~~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:113:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
Main.cpp:141:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
Main.cpp:149:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |   scanf("%d%d %c", &l, &r, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:80:15: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |    lazy[node]=k;
      |               ^
Main.cpp:148:13: note: 'k' was declared here
  148 |   int l, r, k; char c;
      |             ^

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