제출 #771091

#제출 시각아이디문제언어결과실행 시간메모리
771091gagik_2007Crossing (JOI21_crossing)C++17
0 / 100
326 ms4036 KiB
#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=7; 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...