제출 #711194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
711194		Antekb	Crossing (JOI21_crossing)	C++17	0 / 100	485 ms	18284 KiB

Main

#include<bits/stdc++.h>

#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pp pop_back
#define all(x) (x).begin(), (x).end();

using namespace std;

void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
	cerr<<h;
	if(sizeof...(t))cerr<<", ";
	debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<pii>;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N=1<<18;
vector<vi> dobre;
int cod[256];
int czy[N+N][9], lazy[N+N];
bool czy2[N+N][9];
void conv(int i, int j){
	dobre.pb({});
	for(int a=0; a<dobre[0].size(); a++){
		dobre.back().eb((6-dobre[i][a]-dobre[j][a])%3);
	}
}
void create(){
	for(int i=0; i<9; i++){
		for(int j=0; j<dobre[i].size(); j++){
			czy[N+j][i]=dobre[i][j];
		}
		for(int j=N-1; j>0; j--){
			if(czy[j+j][i]==czy[j+j+1][i])czy[j][i]=czy[j+j][i];
			else czy[j][i]=-1;
		}
		for(int j=0; j<N+N; j++)czy2[j][i]=1, lazy[j]=-1;
	}
}
void prop(int v){
	if(lazy[v]==-1 || v>=N)return;
	int l=v+v, r=l+1;
	lazy[l]=lazy[r]=lazy[v];
	for(int i=0; i<9; i++){
		czy2[l][i]=(lazy[v]==czy[l][i]);
		czy2[r][i]=(lazy[v]==czy[r][i]);
	}
}
void ust(int v, int L, int R, int l, int r, int c){
	if(l==L && r==R){
		lazy[v]=c;
		for(int i=0; i<9; i++){
			czy2[v][i]=(lazy[v]==czy[v][i]);
		}
		return;
	}
	int M=(L+R)>>1;
	prop(v);
	if(l<=M)ust(v+v, L, M, l, min(r, M), c);
	if(r>M)ust(v+v+1, M+1, R, max(l, M+1), r, c);
	for(int i=0; i<9; i++){
		czy2[v][i]=czy2[v+v][i]&czy2[v+v+1][i];
	}
}
void ask(){
	bool b=0;
	for(int i=0;i<9; i++){
		if(czy2[1][i])b=1;
	}
	if(b)cout<<"Yes\n";
	else cout<<"No\n";
}
void out(int i){
	assert(N<30);
	for(int j=0; j<N+N; j++){
		deb(j, i, czy[j][i], czy2[j][i], lazy[j]);
	}
}
int main(){
	//ios_base::sync_with_stdio(0);cin.tie(0);
	cod['O']=0;
	cod['I']=1;
	cod['J']=2;
	int n;
	cin>>n;
	string s;
	for(int i=0; i<3; i++){
		cin>>s;
		dobre.pb({});
		for(char c:s)dobre.back().pb(cod[c]);
	}
	for(int i=0; i<2; i++){
		conv(3*i, 3*i+1);
		conv(3*i, 3*i+2);
		conv(3*i+1, 3*i+2);
	}
	//for(vi i:dobre){for(int j:i)cout<<j<<" ";cout<<"\n";}
	int q;
	cin>>q;
	cin>>s;
	create();
	//out(5);
	for(int i=0; i<n; i++)ust(1, 0, N-1, i, i, cod[s[i]]);
	//out(5);
	ask();
	while(q--){
		int l, r;
		char c;
		cin>>l>>r>>c;
		l--, r--;
		ust(1, 0, N-1, l, r, cod[c]);
		ask();
	}
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'void conv(int, int)':
Main.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(int a=0; a<dobre[0].size(); a++){
      |               ~^~~~~~~~~~~~~~~~
Main.cpp: In function 'void create()':
Main.cpp:41:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for(int j=0; j<dobre[i].size(); j++){
      |                ~^~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:101:36: warning: array subscript has type 'char' [-Wchar-subscripts]
  101 |   for(char c:s)dobre.back().pb(cod[c]);
      |                                    ^
Main.cpp:114:53: warning: array subscript has type 'char' [-Wchar-subscripts]
  114 |  for(int i=0; i<n; i++)ust(1, 0, N-1, i, i, cod[s[i]]);
      |                                                     ^
Main.cpp:122:28: warning: array subscript has type 'char' [-Wchar-subscripts]
  122 |   ust(1, 0, N-1, l, r, cod[c]);
      |                            ^

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