Cod sursa(job #1990439)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 11 iunie 2017 20:44:02
Problema Grendizer Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.9 kb
#include <cstdio>
#include <cassert>
#include <algorithm>

using std::sort;
using std::min;
using std::max;

const int MAX_N = 100001;
const int MAX_M = 100001;

struct point_t {
    int s, x;
};

int N;

bool cmpf(const point_t &a, const point_t &b) {
    if (a.s - b.s) return a.s < b.s;
    return a.x < b.x;
}

int how_many(point_t P[], int s, int x) {
    int l, r, sol = -1, mid;
    for (l = 0, r = N; l <= r;) {
        mid = (l + r) >> 1;
        if (P[mid].s < s || (P[mid].s == s && P[mid].x <= x)) {
            sol = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    if (sol < 0) {
        fprintf(stderr, "%d %d -> %d\n", s, x, sol);
    }
    assert(sol >= 0);
    //fprintf(stderr, "s = %d, x = %d sol = %d\n", s, x, sol + 1);
    return sol + 1;
}

point_t P[2][MAX_N + 100];

int main() {
    int M;
    freopen("grendizer.in", "rt", stdin);
    freopen("grendizer.out", "wt", stdout);
    assert(scanf("%d %d", &N, &M) == 2);
    assert(0 < N && N < MAX_N);
    assert(0 < M && M < MAX_M);

    int x, y, r;
    int min_x, max_x, min_y, max_y;
    long long sum_r = 0;
    P[0][0].s = -2000001000;
    P[0][0].x = -2000001000;
    P[1][0].s = -2000001000;
    P[1][0].x = -2000001000;
    P[0][N + 1].s = 2000001000;
    P[0][N + 1].x = 2000001000;
    P[1][N + 1].s = 2000001000;
    P[1][N + 1].x = 2000001000;
    for (int i = 0; i < N; ++i) {
        assert(scanf("%d %d", &x, &y) == 2);
        if (i == 0) {
            min_x = max_x = x;
            min_y = max_y = y;
        } else {
            min_x = min(min_x, x);
            max_x = max(max_x, x);
            min_y = min(min_y, y);
            max_y = max(max_y, y);
        }
        assert(-100000000 < x && x <= 100000000);
        assert(-100000000 < y && y <= 100000000);
        P[0][i + 1].s = x + y;
        P[0][i + 1].x = x;
        P[1][i + 1].s = x - y;
        P[1][i + 1].x = x;
    }
    N = N + 2;
    sort(P[0] + 0, P[0] + N, cmpf);
    sort(P[1] + 0, P[1] + N, cmpf);
    /*
    for (int i = 0; i < N; ++i) {
        fprintf(stderr, "%d %d\n", P[0][i].s, P[0][i].x);
    }
    */
    for (int i = 0; i < M; ++i) {
        assert(scanf("%d %d %d", &x, &y, &r) == 3);
        min_x = min(min_x, x);
        max_x = max(max_x, x);
        min_y = min(min_y, y);
        max_y = max(max_y, y);
        sum_r += r;
        assert(0 < r && r <= 1000000000);
        assert(-100000000 < x && x <= 100000000);
        assert(-100000000 < y && y <= 100000000);
        printf("%d\n", how_many(P[0], x + y + r, x + r) - how_many(P[0], x + y + r, x - 1) +
                       how_many(P[0], x + y - r, x) - how_many(P[0], x + y - r, x - r - 1) +
                       how_many(P[1], x - y + r, x + r - 1) - how_many(P[1], x - y + r, x) +
                       how_many(P[1], x - y - r, x - 1) - how_many(P[1], x - y - r, x - r));
    }
    fprintf(stderr, "(%d %d) (%d %d) %lld\n", min_x, max_x, min_y, max_y, sum_r);
    return 0;
}