Cod sursa(job #1477347)

Utilizator akaprosAna Kapros akapros Data 25 august 2015 23:05:41
Problema Grendizer Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxN 100005
using namespace std;
int n, m, i, j;
pair < int, int > v[2][maxN];
void read()
{
    int x, y;
    freopen("grendizer.in", "r", stdin);
    scanf("%d %d", &n, &m);
    for (i = 1; i <= n; ++ i)
    {
        scanf("%d %d", &x, &y);
        v[0][i] = make_pair(x + y, y);
        v[1][i] = make_pair(x - y, y);
    }

    sort(v[0] + 1, v[0] + n + 1);
    sort(v[1] + 1, v[1] + n + 1);
}
int bs(int q, pair < int, int > val)
{
    int i = 0, p = 1 << 16;
    while (p)
    {
        if (i + p <= n && v[q][i + p] < val)
            i += p;
        p /= 2;
    }
    return i;
}
int BS(int q, pair < int, int > val)
{
    int i = 0, p = 1 << 16;
    while (p)
    {
        if (i + p <= n && v[q][i + p] <= val)
            i += p;
        p /= 2;
    }
    return i;
}
void print()
{
     int x, y, r, sol;
     freopen("grendizer.out", "w", stdout);
     while (m --)
     {
         scanf("%d %d %d", &x, &y, &r);
         sol = BS(0, make_pair(x + y - r, y)) - bs(0, make_pair(x + y - r, y - r));
         sol += BS(0, make_pair(x + y + r, y + r)) - bs(0, make_pair(x + y + r, y));

         sol += bs(1, make_pair(x - y + r, y)) - BS(1, make_pair(x - y + r, y - r));
         sol += bs(1, make_pair(x - y - r, y + r)) - BS(1, make_pair(x - y - r, y));
         printf("%d\n", sol);
     }
}
int main()
{
    read();
    print();
    return 0;
}