Cod sursa(job #1722416)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 28 iunie 2016 00:30:51
Problema Zota & Chidil Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <cstdio>
#include <algorithm>
#define MAXN 100000
struct mycreation{
    int x, y;
}v[13*MAXN+1], u[13*MAXN+1];
inline int myabs(int x){
    if(x<0) return -x;
    else return x;
}
bool cmpx(const mycreation a, const mycreation b){
    if(a.x==b.x) return a.y<b.y;
    else return a.x<b.x;
}
bool cmpy(const mycreation a, const mycreation b){
    if(a.y==b.y) return a.x<b.x;
    else return a.y<b.y;
}
inline int cautbinx(int x, int y, mycreation v[], int n){
    int rez=0, pas;
    for(pas=1<<20; pas; pas>>=1){
        if((rez+pas<=n)&&((v[rez+pas].x<x)||((v[rez+pas].x==x)&&(v[rez+pas].y<=y)))) rez+=pas;
    }
    return rez;
}
inline int cautbiny(int x, int y, mycreation v[], int n){
    int rez=0, pas;
    for(pas=1<<20; pas; pas>>=1){
        if((rez+pas<=n)&&((v[rez+pas].y<y)||((v[rez+pas].y==y)&&(v[rez+pas].x<=x)))) rez+=pas;
    }
    return rez;
}
int main(){
    int n, m, i, k, x, y, p, q, t, r;
    char ch;
    long long ans;
    FILE *fin, *fout;
    fin=fopen("zc.in", "r");
    fout=fopen("zc.out", "w");
    fscanf(fin, "%d%d ", &n, &m);
    k=0;
    for(i=1; i<=n; i++){
        fscanf(fin, "%d%d ", &x, &y);
        for(p=-2; p<=2; p++){
            for(q=-2; q<=2; q++){
                if(myabs(p)+myabs(q)<=2){
                    k++;
                    v[k].x=x+p;
                    v[k].y=y+q;
                    u[k].x=x+p;
                    u[k].y=y+q;
                }
            }
        }
    }
    std::sort(v+1, v+k+1, cmpx);
    std::sort(u+1, u+k+1, cmpy);
    t=1;
    for(i=2; i<=k; i++){
        if((v[i].x!=v[t].x)||(v[i].y!=v[t].y)){
            t++;
            v[t].x=v[i].x;
            v[t].y=v[i].y;
        }
    }
    q=1;
    for(i=2; i<=k; i++){
        if((u[i].x!=u[q].x)||(u[i].y!=u[q].y)){
            q++;
            u[t].x=u[i].x;
            u[t].y=u[i].y;
        }
    }
    x=y=ans=0;
    for(i=1; i<=m; i++){
        ch=fgetc(fin);
        fscanf(fin, "%d ", &r);
        if(ch=='N'){
            ans+=cautbinx(x, y+r, v, t)-cautbinx(x, y, v, t);
            y+=r;
        }else if(ch=='S'){
            ans+=cautbinx(x, y, v, t)-cautbinx(x, y-r, v, t);
            y-=r;
        }else if(ch=='E'){
            ans+=cautbiny(x+r, y, u, q)-cautbiny(x, y, u, q);
            x+=r;
        }else{
            ans+=cautbiny(x, y, u, q)-cautbiny(x-r, y, u, q);
            x-=r;
        }
    }
    fprintf(fout, "%lld\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}