Cod sursa(job #1722503)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 28 iunie 2016 11:58:15
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <utility>
#define BUF_SIZE (1<<13)
#define MAXN 100000
std::pair<int, int>v[13*MAXN+1], u[13*MAXN+1];
int pos=BUF_SIZE;
char buf[BUF_SIZE];
FILE *fin;
inline char nextch(){
    if(pos==BUF_SIZE) fread(buf, BUF_SIZE, 1, fin), pos=0;
    return buf[pos++];
}
inline int read(){
    int x=0, s=1;
    char ch=nextch();
    while((!isdigit(ch))&&(ch!='-')) ch=nextch();
    if(ch=='-'){
        ch=nextch();
        s=-1;
    }
    while(isdigit(ch)){
        x=10*x+ch-'0';
        ch=nextch();
    }
    return x*s;
}
inline int myabs(int x){
    if(x<0) return -x;
    else return x;
}
inline int cautbin(int x, int y, std::pair<int, int> v[], int n){
    int rez=0, pas;
    for(pas=1<<20; pas; pas>>=1){
        if((rez+pas<=n)&&((v[rez+pas].first<x)||((v[rez+pas].first==x)&&(v[rez+pas].second<=y)))) rez+=pas;
    }
    return rez;
}
int main(){
    int n, m, i, k, x, y, p, q, t, r;
    char ch;
    long long ans;
    FILE *fout;
    fin=fopen("zc.in", "r");
    fout=fopen("zc.out", "w");
    n=read();
    m=read();
    k=0;
    for(i=1; i<=n; i++){
        x=read();
        y=read();
        for(p=-2; p<=2; p++){
            for(q=-2; q<=2; q++){
                if((myabs(p)+myabs(q)<=2)&&((x+p!=0)||(y+q!=0))){
                    k++;
                    v[k].first=x+p;
                    v[k].second=y+q;
                }
            }
        }
    }
    std::sort(v+1, v+k+1);
    t=1;
    for(i=2; i<=k; i++){
        if((v[i].first!=v[t].first)||(v[i].second!=v[t].second)){
            t++;
            v[t].first=v[i].first;
            v[t].second=v[i].second;
        }
    }
    for(i=1; i<=t; i++){
        u[i].first=v[i].second;
        u[i].second=v[i].first;
    }
    std::sort(u+1, u+t+1);
    x=y=ans=0;
    for(i=1; i<=m; i++){
        ch=nextch();
        r=read();
        if(ch=='N'){
            ans+=cautbin(x, y+r, v, t)-cautbin(x, y, v, t);
            y+=r;
        }else if(ch=='S'){
            ans+=cautbin(x, y-1, v, t)-cautbin(x, y-r-1, v, t);
            y-=r;
        }else if(ch=='E'){
            ans+=cautbin(y, x+r, u, t)-cautbin(y, x, u, t);
            x+=r;
        }else{
            ans+=cautbin(y, x-1, u, t)-cautbin(y, x-r-1, u, t);
            x-=r;
        }
    }
    fprintf(fout, "%lld\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}