Cod sursa(job #2014333)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 23 august 2017 14:26:43
Problema Zota & Chidil Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 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;
}

inline char getch() {
    char ch = nextch();
    while(!isalpha(ch))
        ch = nextch();
    return ch;
}

const int MAXN = (int) 1e5;

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) {
                   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);
    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;
}