Cod sursa(job #1796969)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 3 noiembrie 2016 21:53:12
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("grendizer.in");
ofstream g("grendizer.out");
pair <int,int> p[1<<17],q[1<<17];
int n,m,i,x,y,r;
int A(int x,int y)
{
    pair <int, int> aux=make_pair(x+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;
}
int B(int x,int y)
{
    pair <int, int> aux=make_pair(x-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()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        f>>p[i].first>>p[i].second;
        q[i]=p[i];
        p[i].first+=p[i].second;
        q[i].first-=q[i].second;
    }
    sort(p+1,p+n+1);
    sort(q+1,q+n+1);
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>r;
        if(r>0) g<<A(x,y+r)-A(x+r,y)+A(x-r+1,y-1)-A(x+1,y-r-1)+B(x+r,y)-B(x,y-r)+B(x-1,y+r-1)-B(x-r-1,y-1)<<'\n';
        else g<<A(x,y)-A(x+1,y-1)<<'\n';
    }
    return 0;
}