# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
904545 | 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<stdio.h>
static int R, C, M, Q;
static int sr, sc;
static char S[100000 + 5];
using namespace std;
#include<bitset>
int 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]|=(1<<px);
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]|=(1<<px);
}
for(int j=2;j<=c;j++){
pref12[j]=pref12[j-1];
if((was[j]==0 and was[j-1]==0) or (was[j]|was[j-1])>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)&1 and (was[j-1]>>1)&1){
pref1[j]++;
}
if((was[j]>>2)&1 and (was[j-1]>>2)&1){
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;
}