// Program pro KSP 24-4-7 sepsal Martin Medvěd Mareš #include #include #include struct xy { // Bod int x, y; }; struct node { // Jeden vrchol stromu struct node *l, *p; // Levý a pravý syn int xmin, xmax; // Minimální a maximální x-ová souřadnice int xmid; // x-ová souřadnice dělící přímky // (body s x=xmid vpravo) int n; // Počet bodů v tomto podstromu struct xy *pt; // Jejich souřadnice: na počátku stavby stromu jsou // body setříděné podle x, v hotovém stromu podle y int *fcl, *fcp; // Ukazatele pro fractional cascading // fcl[i] ukazuje na první bod uložený v levém synovi, // jehož y-ová souřadnice je menší nebo rovna y[i]; // pokud takový bod neexistuje, ukazuje za poslední bod }; struct node *new_node(int n) { struct node *v = malloc(sizeof(*v)); v->n = n; v->l = v->p = NULL; v->pt = malloc(n * sizeof(struct xy)); v->fcl = malloc(n * sizeof(int)); v->fcp = malloc(n * sizeof(int)); return v; } int cmp_x(const void *aa, const void *bb) { const struct xy *a = aa, *b = bb; if (a->x < b->x) return -1; if (a->x > b->x) return 1; return 0; } void build_tree(struct node *v) { if (v->n <= 1) return; // Rozdělíme body podle x-ové souřadnice int mid = v->n / 2; v->xmin = v->pt[0].x; v->xmax = v->pt[v->n - 1].x; v->xmid = v->pt[mid].x; v->l = new_node(mid); v->p = new_node(v->n - mid); memcpy(v->l->pt, v->pt, v->l->n * sizeof(struct xy)); memcpy(v->p->pt, &v->pt[mid], v->p->n * sizeof(struct xy)); // Rekurzivně vybudujeme oba podstromy build_tree(v->l); build_tree(v->p); // Sléváme body z podstromů podle y, přitom počítáme fcl a fcp int li=0, pi=0, i=0; while (li < v->l->n || pi < v->p->n) { v->fcl[i] = li; v->fcp[i] = pi; if (pi == v->p->n || (li < v->l->n && v->l->pt[li].y < v->p->pt[pi].y)) v->pt[i++] = v->l->pt[li++]; else v->pt[i++] = v->p->pt[pi++]; } } // Půlením intervalu najde první bod, jehož y-ová souřadnice je alespoň y int bin_search_y(struct xy *pt, int n, int y) { int l = 0; int r = n; while (l < r) { int mid = (l+r) / 2; if (y == pt[mid].y) return mid; else if (y < pt[mid].y) r = mid; else l = mid + 1; } return r; } // Přepočítá pravý konec intervalu -- pozor, jelikož fc[] jsou ukazatele // na nejbližší větší nebo rovný (což se hodí při úpravě levého konce) // a my bychom potřebovali nejbližší menší nebo rovný, musíme vyzkoušet, // jestli jsme nepřeskočili bod, který už do intervalu nepatří. int fc_right(struct node *son, int *fc, int fcn, int pmax, int ymax) { if (pmax >= fcn) pmax = son->n; else pmax = fc[pmax]; if (pmax > 0 && son->pt[pmax-1].y >= ymax) pmax--; return pmax; } // Rekurzivní vyřizování dotazu: počítáme body, jejichž x-ová souřadnice leží // v intervalu [xmin,xmax) a index v seznamu leží v [pmin,pmax). int subquery(struct node *v, int xmin, int xmax, int pmin, int pmax, int ymax) { // Prázdný průnik s podstromem if (xmin >= xmax || pmin >= pmax) return 0; // Celý podstrom je obsažen v obdélníku, na který se ptáme if (v->xmin >= xmin && v->xmax < xmax) return pmax - pmin; // Rekurze na podstromy return subquery(v->l, xmin, v->xmid, v->fcl[pmin], fc_right(v->l, v->fcl, v->n, pmax, ymax), ymax) + subquery(v->p, v->xmid, xmax, v->fcp[pmin], fc_right(v->p, v->fcp, v->n, pmax, ymax), ymax); } // Spočítá body v intervalu [xmin,xmax) x [ymin,ymax) int query(struct node *v, int xmin, int ymin, int xmax, int ymax) { return subquery(v, xmin, xmax, bin_search_y(v->pt, v->n, ymin), bin_search_y(v->pt, v->n, ymax), ymax); } int main(void) { int N; scanf("%d", &N); struct node *root = new_node(N); // Načteme body a upravíme souřadnice, aby byly unikátní for (int i=0; ipt[i] = (struct xy) { .x = N*x + i, .y = N*y + i }; } // Konstrukce stromu qsort(root->pt, N, sizeof(struct xy), cmp_x); build_tree(root); // Dotazy int x, y, d; while (scanf("%d%d%d", &x, &y, &d) == 3) printf("%d\n", query(root, N*x, N*y, N*(x+d+1), N*(y+d+1))); return 0; }