Pagini recente » Cod sursa (job #1755961) | Cod sursa (job #1719087) | Cod sursa (job #2000090) | Cod sursa (job #477068) | Cod sursa (job #2014358)
#include <bits/stdc++.h>
FILE *fi, *fout;
const int MAXBUF = (int) (1 << 17);
char buf[MAXBUF];
int pbuf = MAXBUF;
inline char nextch() {
if(pbuf == MAXBUF) {
fread(buf, 1, MAXBUF, fi);
pbuf = 0;
}
return buf[pbuf++];
}
inline int getnr() {
char ch = nextch();
char sign = 1;
if(ch == '-')
sign = -1;
while(!isdigit(ch))
ch = nextch();
int nr = 0;
while(isdigit(ch)) {
nr = nr * 10 + ch - '0';
ch = nextch();
}
return nr * sign;
}
inline char getch() {
char ch = nextch();
while(!isalpha(ch))
ch = nextch();
return ch;
}
const int MAXN = (int) 1e5;
const int INF = (int) 2e9 + 1;
std::pair <int, int> lin[MAXN * 13 + 1], col[13 * MAXN + 1];
int sz;
inline int checkl(int l, int c) {
int rez = 0;
for(int pas = 1 << 20; pas; pas >>= 1)
if(rez + pas <= sz && (lin[rez + pas].first < l || (lin[rez + pas].first == l && lin[rez + pas].second <= c)))
rez += pas;
return rez;
}
inline int checkc(int l, int c) {
int rez = 0;
for(int pas = 1 << 20; pas; pas >>= 1)
if(rez + pas <= sz && (col[rez + pas].first < c || (col[rez + pas].first == c && col[rez + pas].second <= l)))
rez += pas;
return rez;
}
int main() {
int i, n, m, l, c;
fi = fopen("zc.in" ,"r");
fout = fopen("zc.out" ,"w");
n = getnr();
m = getnr();
for(i = 1; i <= n; i++) {
c = getnr();
l = getnr();
for(int dl = -2; dl <= 2; dl++)
for(int dc = -2; dc <= 2; dc++)
if(std::abs(dl) + std::abs(dc) <= 2 && !(l + dl == 0 && c + dc == 0)) {
lin[++sz] = {l + dl, c + dc};
col[sz] = {c + dc, l + dl};
}
}
std::sort(lin + 1, lin + sz + 1);
std::sort(col + 1, col + sz + 1);
int sz1 = 0;
lin[0] = {-INF, -INF};
for(i = 1; i <= sz; i++)
if(lin[i].first != lin[i - 1].first || lin[i].second != lin[i - 1].second)
lin[++sz1] = lin[i];
col[0] = {-INF, -INF};
sz1 = 0;
for(i = 1; i <= sz; i++)
if(col[i].first != col[i - 1].first || col[i].second != col[i - 1].second)
col[++sz1] = col[i];
sz = sz1;
long long ans = 0;
l = c = 0;
for(i = 1; i <= m; i++) {
char ch = getch();
int x = getnr();
if(ch == 'N') {
ans += checkc(l + x, c) - checkc(l, c);
l += x;
}
if(ch == 'E') {
ans += checkl(l, c + x) - checkl(l, c);
c += x;
}
if(ch == 'S') {
ans += checkc(l - 1, c) - checkc(l - x - 1, c);
l -= x;
}
if(ch == 'V') {
ans += checkl(l, c - 1) - checkl(l, c - x - 1);
c -= x;
}
}
fprintf(fout,"%lld" ,ans);
fclose(fi);
fclose(fout);
return 0;
}