Cod sursa(job #1758906)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 18 septembrie 2016 01:34:03
Problema Grendizer Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>
#include <utility>
#include <algorithm>

#define x first
#define y second

#define MAXN 100000

std::pair <int, int> p[MAXN+1], q[MAXN+1];
int n;

inline int f(int x, int y){
    std::pair <int, int> aux;
    aux.x=x+y;
    aux.y=y;
    int rez=0;
    for(int pas=1<<16; pas; pas>>=1)
        if((rez+pas<=n)&&(p[rez+pas]<=aux))
            rez+=pas;
    return rez;
}

inline int g(int x, int y){
    std::pair <int, int> aux;
    aux.x=x-y;
    aux.y=y;
    int rez=0;
    for(int pas=1<<16; pas; pas>>=1)
        if((rez+pas<=n)&&(q[rez+pas]<=aux))
            rez+=pas;
    return rez;
}

int main(){
    int m, i, x, y, r;
    FILE *fin, *fout;
    fin=fopen("grendzier.in", "r");
    fout=fopen("grendzier.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    for(i=1; i<=n; i++){
        fscanf(fin, "%d%d", &p[i].x, &p[i].y);
        q[i]=p[i];
        p[i].x+=p[i].y;
        q[i].x-=q[i].y;
    }
    std::sort(p+1, p+n+1);
    std::sort(q+1, q+n+1);
    for(i=1; i<=m; i++){
        fscanf(fin, "%d%d%d", &x, &y, &r);
        if(r>0) fprintf(fout, "%d\n", f(x, y+r)-f(x+r, y)+f(x-r+1, y-1)-f(x+1, y-r-1)+g(x+r, y)-g(x, y-r)+g(x-1, y+r-1)-g(x-r-1, y-1));
        else fprintf(fout, "%d\n", f(x, y)-f(x+1, y-1));
    }
    fclose(fin);
    fclose(fout);
    return 0;
}