# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
904535 | vjudge1 | Land of the Rainbow Gold (APIO17_rainbow) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bitset>
bitset<3> was[200001];
int pref1[200005];
int pref2[200005];
int pref12[200005];
void init(int r,int c,int sr,int sc,int m,char* s){
int px=sr,py=sc;
was[py][px]=1;
for(int i=0;i<m;i++){
char u=s[i];
if(u=='S'){
px++;
}else if(u=='N'){
px--;
}else if(u=='E'){
py++;
}else{
py--;
}
// cout<<px<<' '<<py<<endl;
was[py][px]=1;
}
for(int j=2;j<=c;j++){
pref12[j]=pref12[j-1];
if((was[j].count()==0 and was[j-1].count()==0) or (was[j]|was[j-1]).count()>0){
}else{
pref12[j]++;
}
}
for(int j=2;j<=c;j++){
pref1[j]=pref1[j-1];
pref2[j]=pref2[j-1];
if(was[j][1] and was[j-1][1]){
pref1[j]++;
}
if(was[j][2] and was[j-1][2]){
pref2[j]++;
}
}
}
int colour(int lx,int ly,int rx,int ry){
if(lx<rx){
return pref12[ry]-pref12[ly];
}else if(lx==1){
return pref1[ry]-pref1[ly];
}else{
return pref2[ry]-pref2[ly];
}
}
int main() {
scanf("%d %d %d %d", &R, &C, &M, &Q);
scanf("%d %d", &sr, &sc);
if (M > 0) {
scanf(" %s ", S);
}
init(R, C, sr, sc, M, S);
int query;
for (query = 0; query < Q; query++) {
int ar, ac, br, bc;
scanf("%d %d %d %d", &ar, &ac, &br, &bc);
printf("%d\n", colour(ar, ac, br, bc));
}
return 0;
}