Cod sursa(job #1722495)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 28 iunie 2016 11:52:31
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.82 kb
#include <cstdio>
#include <algorithm>
#include <cctype>
#define BUF_SIZE (1<<13)
#define MAXN 100000
int pos=BUF_SIZE;
char buf[BUF_SIZE];
FILE *fin;
struct mycreation{
    int x, y;
}v[13*MAXN+1], u[13*MAXN+1];
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;
}
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 *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].x=x+p;
                    v[k].y=y+q;
                }
            }
        }
    }
    std::sort(v+1, v+k+1, cmpx);
    /*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;
        }
    }
    for(i=1; i<=t; i++){
        u[i].x=v[i].x;
        u[i].y=v[i].y;
    }
    std::sort(u+1, u+t+1, cmpy);
    x=y=ans=0;
    for(i=1; i<=m; i++){
        ch=nextch();
        r=read();
        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-1, v, t)-cautbinx(x, y-r-1, v, t);
            y-=r;
        }else if(ch=='E'){
            ans+=cautbiny(x+r, y, u, t)-cautbiny(x, y, u, t);
            x+=r;
        }else{
            ans+=cautbiny(x-1, y, u, t)-cautbiny(x-r-1, y, u, t);
            x-=r;
        }
    }
    fprintf(fout, "%lld\n", ans);*/
    fclose(fin);
    fclose(fout);
    return 0;
}