Cod sursa(job #2869323)

Utilizator raulandreipopRaul-Andrei Pop raulandreipop Data 11 martie 2022 14:03:07
Problema Grendizer Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.63 kb
#include <bits/stdc++.h>
#define f first
#define s second

using namespace std;

struct pct{
    bool friend operator<(const pct& p1, const pct& p2)
    {
        return p1.x < p2.x;
    }
    int x, y , ind;
};

map<int, set<pct>> diag1;
map<int, set<pct>> diag2;
map<int, bool> isdiag1;
map<int, bool> isdiag2;
vector<int> d1, d2;
map<pair<int, int> , int> target;

int main ()
{
    freopen("grendizer.in", "r", stdin);
    freopen("grendizer.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        diag1[x-y].insert({x, y, 0});
        diag2[x+y].insert({x, y, 0});
        target[{x, y}]++;
        if (!isdiag1[x-y])
        {
            isdiag1[x-y] = 1;
            d1.push_back(x-y);
        }
        if (!isdiag2[x+y])
        {
            isdiag2[x+y] = 1;
            d2.push_back(x+y);
        }
    }
    for (auto d : d1)
    {
        int ind = 1;
        set<pct>::iterator it;
        set<pct> newset;
        for (it = diag1[d].begin(); it != diag1[d].end(); it++)
        {
            newset.insert({(*it).x, (*it).y, ind});
            ind++;
        }
        diag1[d] = newset;
        diag1[d].insert({(int)-1e9 - 1, 0, 0});
        diag1[d].insert({(int)1e9 + 1, 0, ind});
    }
    for (auto d : d2)
    {
        int ind = 1;
        set<pct>::iterator it;
        set<pct> newset;
        for (it = diag2[d].begin(); it != diag2[d].end(); it++)
        {
            newset.insert({(*it).x, (*it).y, ind});
            ind++;
        }
        diag2[d] = newset;
        diag2[d].insert({(int)-1e9 - 1, 0, 0});
        diag2[d].insert({(int)1e9 + 1, 0, ind});
    }
    int x, y, r;
    while (m--)
    {
        int ans = 0;
        cin >> x >> y >> r;

        if (!diag1[x - r - y].empty()){
            set<pct>::iterator u = diag1[x - r - y].lower_bound({x, y});
            set<pct>::iterator d = diag1[x - r - y].lower_bound({x - r, y});
            if ((*u).x > x) u--;
            ans += (*u).ind - (*d).ind + 1;
        }
        else {
            diag1.erase(x - r - y);
        }


        if (!diag1[x + r - y].empty()){
            set<pct>::iterator u = diag1[x + r - y].lower_bound({x + r, y});
            set<pct>::iterator d = diag1[x + r - y].lower_bound({x, y});
            if ((*u).x > x + r) u--;
            ans += (*u).ind - (*d).ind + 1;
        }
        else {
            diag1.erase(x + r - y);
        }
        if (!diag2[x + r + y].empty()){
            set<pct>::iterator u = diag2[x + r + y].lower_bound({x + r, y});
            set<pct>::iterator d = diag1[x + r + y].lower_bound({x, y});
            if ((*u).x > x + r) u--;
            ans += (*u).ind - (*d).ind + 1;
        }
        else {
            diag2.erase(x + r + y);
        }
        if (!diag2[x - r + y].empty()){
            set<pct>::iterator u = diag2[x - r + y].lower_bound({x, y});
            set<pct>::iterator d = diag2[x - r + y].lower_bound({x - r, y});
            if ((*u).x > x) u--;
            ans += (*u).ind - (*d).ind + 1;
        }
        else {
            diag2.erase(x - r + y);
        }
        if (target[{x - r, y}] != 0)
        {
            ans -= target[{x - r, y}];
        }
        else target.erase({x - r, y});

        if (target[{x + r, y}] != 0)
        {
            ans -= target[{x + r, y}];
        }
        else target.erase({x + r, y});

        if (target[{x, y - r}] != 0)
        {
            ans -= target[{x, y - r}];
        }
        else target.erase({x, y - r});

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