Cod sursa(job #2868559)

Utilizator raulandreipopRaul-Andrei Pop raulandreipop Data 11 martie 2022 00:07:42
Problema Grendizer Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.69 kb
#include <bits/stdc++.h>

using namespace std;

struct pct{
    int x, y;
};
int n, m;

bool checkd1 (pct a, int vl)
{
    if (a.x - a.y == vl)return true;
    return false;
}

bool checkd2 (pct a, int vl)
{
    if (a.x + a.y == vl)return true;
    return false;
}

bool cmpd1 (const pct& p1, const pct& p2)
{
    if (p1.x - p1.y == p2.x - p2.y)
    {
        return p1.x < p2.x;
    }
    else return p1.x - p1.y < p2.x - p2.y;
}

bool cmpd2 (const pct& p1, const pct& p2)
{
    if (p1.x + p1.y == p2.x + p2.y)
    {
        return p1.x < p2.x;
    }
    else return p1.x + p1.y < p2.x + p2.y;
}

pct a[200200];
pct b[200200];

int cbd1 (int dif, int x)
{
    pct p = {x, x - dif};
    int l = 1, h = n;
    while (l < h)
    {
        int m = (l + h) / 2;
        if (cmpd1(a[m], p) == 1) l = m + 1;
        else h = m;
    }
    return l;
}

int cbd2 (int sum, int x)
{
    pct p = {x, sum - x};
    int l = 1, h = n;
    while (l < h)
    {
        int m = (l + h) / 2;
        if (cmpd2(b[m], p) == 1) l = m + 1;
        else h = m;
    }
    return l;
}

map<pair<int, int> , bool> target;

int main() {
    freopen("grendizer.in", "r", stdin);
    freopen("grendizer.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].x >> a[i].y;
        b[i] = a[i];
        target[{a[i].x, a[i].y}] = 1;
    }
    sort(a + 1, a + 1 + n, cmpd1);
    sort(b + 1, b + 1 + n, cmpd2);

    while (m--)
    {
        int x, y, r;
        cin >> x >> y >> r;
        int ans = 0;
        int u, d;
        u = cbd1(x - r - y, x);
        d = cbd1(x - r - y, x - r);
        if (!checkd1(a[u], x - r - y)) u--;
        if (checkd1(a[d], x - r - y) && checkd1(a[u], x - r - y))
            ans += u - d + 1;

        u = cbd2(x + r + y, x + r);
        d = cbd2(x + r + y, x);
        if (!checkd2(b[u], x + r + y)) u--;
        if (checkd2(b[d], x + r + y) && checkd2(b[u], x + r + y))
            ans += u - d + 1;

        u = cbd1(x + r - y, x + r);
        d = cbd1(x + r - y, x);
        if (!checkd1(a[u], x + r - y)) u--;
        if (checkd1(a[d], x + r - y) && checkd1(a[u], x + r - y))
            ans += u - d + 1;

        u = cbd2(x - r + y, x);
        d = cbd2(x - r + y, x - r);
        if (!checkd2(b[u], x - r + y)) u--;
        if (checkd2(b[d], x - r + y) && checkd2(b[u], x - r + y))
            ans += u - d + 1;

        if (target[{x, y + r}] == 1) ans--;
        else target.erase({x, y + r});
        if (target[{x + r, y}] == 1) ans--;
        else target.erase({x + r, y});
        if (target[{x - r, y}] == 1) ans--;
        else target.erase({x - r, y});
        if (target[{x, y - r}] == 1) ans--;
        else target.erase({ x, y - r });
        cout << ans << '\n';
    }
    return 0;
}