Cod sursa(job #2014358)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 23 august 2017 14:56:57
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.94 kb
#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;
}