Cod sursa(job #1471720)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 14 august 2015 23:23:28
Problema Grendizer Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <cstdio>
#include <algorithm>

#define PII pair < int , int >
#define F first
#define S second

using namespace std;

const int Nmax = 100010;

int n , m , limit;
PII d[2][Nmax];

int search_(int ind , PII info , int mode)
{
    int i , step = limit;

    for (i = 0; step; step >>= 1)
        if (i + step <= n && d[ind][i+step] < info)
            i += step;

    return i + mode * (i < n && d[ind][i+1] == info);
}

int main()
{
    freopen("grendizer.in","r",stdin);
    freopen("grendizer.out","w",stdout);

    scanf("%d %d", &n, &m);

    for (limit = 1; limit < n; limit <<= 1);

    for (int i = 1; i <= n; ++i)
    {
        int x , y;
        scanf("%d %d", &x, &y);
        d[0][i] = {x + y , y}; /// dP
        d[1][i] = {x - y , y}; /// dS
    }

    sort(d[0] + 1 , d[0] + n + 1);
    sort(d[1] + 1 , d[1] + n + 1);

    for ( ; m ; --m)
    {
        int x , y , r;
        scanf("%d %d %d", &x, &y, &r);

        int ans = 0;

        /// dP
        ans += search_(0 , {x + (y + r) , y + r} , 1) - search_(0 , {(x + r) + y , y} , 0);
        if (ans && !r) ans++;
        ans += search_(0 , {(x - r) + y , y} , 1) - search_(0 , {x + (y - r) , y - r} , 0);
        /// dS
        ans += search_(1 , {x - (y + r) , y + r - 1} , 1) - search_(1 , {(x - r) - y , y + 1} , 0);
        ans += search_(1 , {(x + r) - y , y - 1} , 1) - search_(1 , {x - (y - r) , y - r + 1} , 0);

        printf("%d\n", ans);
    }

    return 0;
}