Cod sursa(job #2841096)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 29 ianuarie 2022 12:04:15
Problema Zota & Chidil Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <algorithm>
#include <cstdio>

#define MAX 8000000

using namespace std;

struct punct {
    int x, y;
};

char f[MAX];
int pos = 0;

int dx[13] = {-2, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 2};
int dy[13] = {0, -1, 0, 1, -2, -1, 0, 1, 2, -1, 0, 1, 0};
punct ox[1300005], oy[1300005];
int n, m, l = 0;
long long ans = 0;
punct chidil;

void r(int &nr) {
    nr = 0;
    int sign = 1;
    while (f[pos] < '0' || f[pos] > '9') {
        if (f[pos] == '-')
            sign = 0;
        pos++;
    }
    while (f[pos] >= '0' && f[pos] <= '9')
        nr = nr * 10 + f[pos++] - '0';
    if (sign == 0)
        nr = -nr;
}

void rch(char &ch) {
    while (f[pos] < 'A' || f[pos] > 'Z')
        pos++;
    ch = f[pos];
    pos++;
}

bool cmp(punct a, punct b) { return a.y < b.y || (a.y == b.y && a.x < b.x); }

bool cmp2(punct a, punct b) { return !cmp(b, a); }

int bs(punct *v, punct val) {
    int st = 1, dr = l, mid, last = 0;
    while (st <= dr) {
        mid = (st + dr) / 2;
        if (cmp2(v[mid], val)) {
            last = mid;
            st = mid + 1;
        } else
            dr = mid - 1;
    }
    return last;
}

punct transform(punct x) {
    punct y;
    y.x = x.y;
    y.y = x.x;
    return y;
}

int main() {
    freopen("zc.in", "r", stdin);
    freopen("zc.out", "w", stdout);
    fread(f, 1, MAX, stdin);

    r(n);
    r(m);
    for (int i = 1; i <= n; i++) {
        int x, y;
        r(y);
        r(x);
        for (int j = 0; j < 13; j++) {
            l++;
            ox[l].x = x + dx[j];
            ox[l].y = y + dy[j];

            oy[l].y = x + dx[j];
            oy[l].x = y + dy[j];
        }
    }

    sort(ox + 1, ox + 1 + l, cmp);
    sort(oy + 1, oy + 1 + l, cmp);

    for (int i = 1; i <= m; i++) {
        punct dest;
        char dir;
        int dist;
        rch(dir);
        r(dist);

        if (dir == 'S') {
            dest = chidil;
            dest.x -= dist;
            ans += bs(ox, chidil) - bs(ox, dest);
        } else if (dir == 'N') {
            dest = chidil;
            dest.x += dist;
            ans += bs(ox, dest) - bs(ox, chidil);

        } else if (dir == 'V') {
            dest = chidil;
            dest.y -= dist;
            ans += bs(oy, transform(chidil)) - bs(oy, transform(dest));
        } else {
            dest = chidil;
            dest.y += dist;
            ans += bs(oy, transform(dest)) - bs(oy, transform(chidil));
        }
        chidil = dest;
    }
    printf("%lld\n", ans);
    return 0;
}