Cod sursa(job #1990432)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 11 iunie 2017 20:24:51
Problema Grendizer Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

ofstream fout ("grendizer.out");

class InputReader {
	public:
        InputReader() {}
        InputReader(const char *name) {
            fin = fopen(name, "r");
			buffpos = Size - 1;
        }
        inline InputReader &operator >>(int &n) {
			char ch = nextpos();
            while((ch < '0' || ch > '9') && ch != '-') {
                ch = nextpos();
            }

            int semn = 1;
            if (ch == '-') {
                semn = -1; ch = nextpos();
            }

            n = 0;
            while('0' <= ch && ch <= '9') {
                n = n * 10 + ch - '0';
                ch = nextpos();
            }
            n *= semn;
            return *this;
        }
    private:
        FILE *fin;
        static const int Size = 1 << 19;
        int buffpos;
        char buff[Size];

        inline char nextpos() {
            ++ buffpos;
            if(buffpos == Size) {
                buffpos = 0;
                fread(buff, Size, 1, fin);
            }
			return buff[ buffpos ];
        }
} fin ("grendizer.in");

const int nmax = 1e5;

int n;
unordered_map <int, vector< int >> mpx, mpy;

int clin (const vector< int > &k, int pos) {
    return upper_bound(k.begin(), k.end(), pos) - k.begin();
}

int main() {
    int m;
    fin >> n >> m;

    for (int i = 1; i <= n; ++ i) {
        int x, y;
        fin >> x >> y;
        mpx[x + y].push_back(x - y);
        mpy[x - y].push_back(x + y);
    }

    for (auto &i : mpx) sort(i.second.begin(), i.second.end());
    for (auto &i : mpy) sort(i.second.begin(), i.second.end());

    for (int i = 1; i <= m; ++ i) {
        int x, y, r;
        fin >> x >> y >> r;

        int sol = 0;
        if (mpx.find(x + y - r) != mpx.end())
            sol += clin(mpx[x + y - r], x - y + r) - clin(mpx[x + y - r], x - y - r - 1);
        if (mpx.find(x + y + r) != mpx.end())
            sol += clin(mpx[x + y + r], x - y + r) - clin(mpx[x + y + r], x - y - r - 1);

        if (mpy.find(x - y + r) != mpy.end())
            sol += clin(mpy[x - y + r], x + y + r - 1) - clin(mpy[x - y + r], x + y - r);
        if (mpy.find(x - y - r) != mpy.end())
            sol += clin(mpy[x - y - r], x + y + r - 1) - clin(mpy[x - y - r], x + y - r);

        fout << sol << "\n";
    }

    fout.close();
    return 0;
}