#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"
const int X[] = {1, 0, -1, 0};
const int Y[] = {0, 1, 0, -1};
const int INF = 1e9;
struct fenwick_tree_2D {
int m, n;
vector<vector<int> > bit;
void init(int _m, int _n) {
m = _m;
n = _n;
bit.resize(m+1);
for (int i=0; i<=m; ++i)
bit[i].resize(n+1);
}
void add(int x, int y) {
if (!bit[x][y])
++bit[x][y];
}
void process() {
for (int i=1; i<=m; ++i) {
for (int j=1; j<=n; ++j)
bit[i][j] += bit[i-1][j] + bit[i][j-1] - bit[i-1][j-1];
}
}
int get(int x1, int y1, int x2, int y2) {
if (x1>x2 || y1>y2)
return 0;
return bit[x2][y2] - bit[x2][y1-1] - bit[x1-1][y2] + bit[x1-1][y1-1];
}
};
int m, n, min_x, max_x, min_y, max_y;
vector<pair<int, int> > snake;
bool visited[52][52];
fenwick_tree_2D T1, T2, R, C;
void add(pair<int, int> p) {
T1.add(p.first, p.second);
for (int i=0; i<4; ++i) {
T2.add(p.first, p.second);
p.first += X[i];
p.second += Y[i];
}
C.add(p.first, p.second);
C.add(p.first, p.second+1);
R.add(p.first, p.second);
R.add(p.first+1, p.second);
}
void init(int _R, int _C, int sr, int sc, int M, char *S) {
m = _R;
n = _C;
max_x = max_y = -INF;
min_x = min_y = INF;
snake.resize(M+1);
snake[0] = {sr, sc};
for (int i=1; i<=M; ++i) {
snake[i] = snake[i-1];
if (S[i-1]=='N')
--snake[i].first;
else if (S[i-1]=='S')
++snake[i].first;
else if (S[i-1]=='W')
--snake[i].second;
else
++snake[i].second;
}
sort(snake.begin(), snake.end());
snake.resize(unique(snake.begin(), snake.end()) - snake.begin());
T1.init(m+1, n+1);
T2.init(m+1, n+1);
R.init(m+1, n+1);
C.init(m+1, n+1);
for (auto p : snake) {
min_x = min(min_x, p.first);
max_x = max(max_x, p.first);
min_y = min(min_y, p.second);
max_y = max(max_y, p.second);
add(p);
}
T1.process();
T2.process();
R.process();
C.process();
}
int colour(int x1, int y1, int x2, int y2) {
int v = T2.get(x1+1, y1+1, x2, y2);
int e = R.get(x1+1, y1, x2, y2) + C.get(x1, y1+1, x2, y2);
// debug(R.get(x1+1, y1+1, x2, y2-1));
int res = e - v + 1;
if (x1<min_x && max_x<x2 && y1<min_y && max_y<y2)
++res;
res -= T1.get(x1, y1, x2, y2);
return res;
}
int main() {
freopen("rainbow.in", "r", stdin);
// freopen("rainbow.out", "w", stdout);
int R, C, M, Q, sr, sc;
static char S[100 + 5];
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;
}
Compilation message
rainbow.cpp: In function 'int main()':
rainbow.cpp:124:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("rainbow.in", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
rainbow.cpp:128:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &R, &C, &M, &Q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
rainbow.cpp:129:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &sr, &sc);
~~~~~^~~~~~~~~~~~~~~~~~~
rainbow.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s ", S);
~~~~~^~~~~~~~~~~
rainbow.cpp:139:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &ar, &ac, &br, &bc);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/tmp/ccitzI6O.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccAQDcqu.o:rainbow.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
