이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=2e5+7;
ll n,m,k;
vector<string>b;
string s1,s2,s3,tt;
char vs[3]={'J', 'O', 'I'};
int vls[500];
const ll B=13;
ll powB[N];
ll powBsum[N];
ll t[4*N];
ll lazy[8*N];
vector<ll>hashes;
ll str_hash(const string& s) {
ll ans=0;
ll cur=1;
for(char c:s){
ans+=vls[c]*cur;
ans%=MOD;
cur*=B;
cur%=MOD;
}
return ans;
}
void push(int v, int tl, int tr) {
if(lazy[v]!=0){
lazy[v]--;
t[v]=lazy[v]*powB[tl]*powBsum[tr-tl];
t[v]%=MOD;
lazy[v]++;
lazy[2*v]=lazy[v];
lazy[2*v+1]=lazy[v];
lazy[v]=0;
}
}
void build(int v, int tl, int tr) {
if(tl==tr){
t[v]=vls[tt[tl]]*powB[tl];
t[v]%=MOD;
}
else{
int tm=(tl+tr)/2;
build(2*v,tl,tm);
build(2*v+1,tm+1,tr);
t[v]=t[2*v]+t[2*v+1];
t[v]%=MOD;
}
}
void update(int v, int tl, int tr, int l, int r, char c) {
push(v,tl,tr);
if(l>r)return;
if(tl==l&&tr==r){
lazy[v]=vls[c]+1;
push(v,tl,tr);
}
else{
push(v,tl,tr);
int tm=(tl+tr)/2;
update(2*v,tl,tm,l,min(r,tm),c);
update(2*v+1,tm+1,tr,max(l,tm+1),r,c);
t[v]=t[2*v]+t[2*v+1];
push(v,tl,tr);
}
}
string cross(const string& a, const string& b) {
string c;
for(int i=0;i<a.size();i++){
if(a[i]==b[i]){
c+=a[i];
}
else {
c+=vs[3-vls[a[i]]-vls[b[i]]];
}
}
return c;
}
bool compare(){
for(ll h:hashes){
if(h==t[1])return true;
}
return false;
}
void precalc() {
vls['J']=0;
vls['O']=1;
vls['I']=2;
powB[0]=1;
powBsum[0]=1;
for(int i=1;i<N;i++){
powB[i]=powB[i-1]*B;
powB[i]%=MOD;
powBsum[i]=powBsum[i-1]+powB[i];
powBsum[i]%=MOD;
}
}
int main() {
precalc();
cin>>n;
cin>>s1>>s2>>s3;
b.push_back(s1);
b.push_back(s2);
b.push_back(s3);
b.push_back(cross(s1,s2));
b.push_back(cross(s2,s3));
b.push_back(cross(s1,s3));
b.push_back(cross(b[3],b[4]));
b.push_back(cross(b[3],b[5]));
b.push_back(cross(b[4],b[5]));
for(string& s:b){
hashes.push_back(str_hash(s));
}
cin>>m;
cin>>tt;
build(1,0,n-1);
if(compare()){
cout<<"Yes\n";
}
else cout<<"No\n";
for(int i=0;i<m;i++){
int l,r;
char c;
cin>>l>>r>>c;
l--,r--;
update(1,0,n-1,l,r,c);
// for(int i=0;i<100;i++)cout<<t[i]<<" ";cout<<endl;
// for(int i=0;i<100;i++)cout<<lazy[i]<<" ";cout<<endl;
if(compare()){
cout<<"Yes\n";
}
else cout<<"No\n";
}
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'll str_hash(const string&)':
Main.cpp:29:18: warning: array subscript has type 'char' [-Wchar-subscripts]
29 | ans+=vls[c]*cur;
| ^
Main.cpp: In function 'void build(int, int, int)':
Main.cpp:51:24: warning: array subscript has type 'char' [-Wchar-subscripts]
51 | t[v]=vls[tt[tl]]*powB[tl];
| ^
Main.cpp: In function 'void update(int, int, int, int, int, char)':
Main.cpp:67:21: warning: array subscript has type 'char' [-Wchar-subscripts]
67 | lazy[v]=vls[c]+1;
| ^
Main.cpp: In function 'std::string cross(const string&, const string&)':
Main.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for(int i=0;i<a.size();i++){
| ~^~~~~~~~~
Main.cpp:87:29: warning: array subscript has type 'char' [-Wchar-subscripts]
87 | c+=vs[3-vls[a[i]]-vls[b[i]]];
| ^
Main.cpp:87:39: warning: array subscript has type 'char' [-Wchar-subscripts]
87 | c+=vs[3-vls[a[i]]-vls[b[i]]];
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |