Submission #421498

#	Time	Username	Problem	Language	Result	Execution time	Memory
421498		jamezzz	Crossing (JOI21_crossing)	C++17	100 / 100	661 ms	47432 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#include <ext/rope>
using namespace __gnu_cxx;

typedef tree<long long, null_type, less<long long>,
rb_tree_tag, tree_order_statistics_node_update> pbds;
//less_equal for identical elements

#define DEBUG

#ifdef DEBUG
#define debug(...) printf(__VA_ARGS__);
#else
#define debug(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;

#define base 5
#define mod 1000000007

int n,q,l,r;
ll val[4][200005],pw[200005];
char c;
vector<vi> v;
set<ll> h;

struct node{
	int s,e,m,lz;ll v;
	node *l,*r;
	node(int _s,int _e){
		s=_s;e=_e;m=(s+e)/2;lz=0;v=0;
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	void ppo(){
		if(lz==0)return;
		v=val[lz][(e-s+1)];
		if(s!=e)l->lz=lz,r->lz=lz;
		lz=0;
	}
	void up(int x,int y,int nv){
		ppo();
		if(s==x&&e==y){
			lz=nv;return;
		}
		if(y<=m)l->up(x,y,nv);
		else if(x>m)r->up(x,y,nv);
		else l->up(x,m,nv),r->up(m+1,y,nv);
		l->ppo();r->ppo();
		v=(l->v*pw[r->e-r->s+1]+r->v)%mod;
	}
	ll qry(){
		ppo();return v;
	}
}*root;

int to(char c){
	if(c=='J')return 0;
	else if(c=='O')return 1;
	else return 2;
}

int main(){
	sf("%d",&n);
	for(int j=0;j<3;++j){
		v.push_back(vi());
		for(int i=0;i<n;++i){
			scanf(" %c",&c);
			int x=to(c);
			v.back().pb(x);
		}
	}
	for(int i=-2;i<=2;++i){
		for(int j=-2;j<=2;++j){
			for(int k=-2;k<=2;++k){
				if((i+j+k)%3!=1)continue;
				v.push_back(vi());
				for(int l=0;l<n;++l){
					int nw=v[0][l]*i+v[1][l]*j+v[2][l]*k+9;
					v.back().pb(nw%3);
				}
			}
		}
	}
	for(vi x:v){
		ll hash=0;
		for(int i=0;i<n;++i){
			hash*=base;
			hash+=(x[i]+1);
			hash%=mod;
		}
		h.insert(hash);
	}
	for(int i=1;i<=3;++i){
		for(int j=1;j<=n;++j){
			val[i][j]=(val[i][j-1]*base+i)%mod;
		}
	}
	pw[0]=1;
	for(int i=1;i<=n;++i)pw[i]=(pw[i-1]*base)%mod;
	root=new node(0,n-1);
	sf("%d",&q);
	for(int i=0;i<n;++i){
		sf(" %c",&c);
		int x=to(c)+1;
		root->up(i,i,x);
	}
	if(h.count(root->qry()))pf("Yes\n");
	else pf("No\n");
	for(int i=0;i<q;++i){
		sf("%d%d",&l,&r);
		sf(" %c",&c);
		int x=to(c)+1;
		root->up(l-1,r-1,x);
		if(h.count(root->qry()))pf("Yes\n");
		else pf("No\n");
	}
}

/*
4
JOJO
JJOI
OJOO
3
IJOJ
1 4 O
2 2 J
2 4 I
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:86:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |  sf("%d",&n);
      |    ^
Main.cpp:90:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |    scanf(" %c",&c);
      |    ~~~~~^~~~~~~~~~
Main.cpp:124:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |  sf("%d",&q);
      |    ^
Main.cpp:126:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |   sf(" %c",&c);
      |     ^
Main.cpp:133:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |   sf("%d%d",&l,&r);
      |     ^
Main.cpp:134:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |   sf(" %c",&c);
      |     ^

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