Language: C++

1 2
#include <bits/stdc++.h>

const int MAX_N = 500005;
const int MAX_R = 1000000000;
int N;

struct pt {
	int x, y, id;

	bool operator<(const pt& b) const { return id < b.id; }
} pts[MAX_N];

struct node {
	std::vector<pt> pts;
	pt mid;
	node* l, *r;
} root;

std::set<pt> ans;

void build(int st, int en, int dep, node* n) {
	if (en - st == 1) {
		n->pts.push_back(pts[st]);
		n->mid = pts[st];
		return;
	} else if (en - st == 0) {
		return;
	}
	int mid = (st + en) / 2;
	std::sort(pts + st, pts + en, [dep](const pt& a, const pt& b) {
		bool typ[2] = {a.x < b.x, a.y < b.y};
		bool qal[2] = {a.x != b.x, a.y != b.y};
		if (qal[dep]) return typ[dep];
		return typ[!dep];
	});

	n->pts = std::vector<pt>(pts + st, pts + en);
	n->l = new node;
	n->r = new node;
	n->mid = pts[mid];

	build(st, mid, (dep + 1) % 2, n->l);
	build(mid, en, (dep + 1) % 2, n->r);
}

bool pis(pt tl, pt br, pt p) {
	return p.x >= tl.x && p.x <= br.x && p.y <= tl.y && p.y >= br.y;
}

bool aFullyContainsB(pt tla, pt bra, pt tlb, pt brb) {
	return pis(tla, bra, tlb) && pis(tla, bra, brb);
}

bool intersect(pt tla, pt bra, pt tlb, pt brb) {
	return tla.x < brb.x && bra.x > tlb.x && tla.y > brb.y && bra.y < tlb.y;
}

void query(int stx, int enx, int sty, int eny, int nstx, int nenx, int nsty, int neny, node* n, int dep) {
	if (!n) return;

	// printf("%d %d %d %d %d %d %d %d\n", stx, enx, sty, eny, nstx, nenx, nsty, neny);
	bool inter = intersect({stx, eny, 0}, {enx, sty, 0}, {nstx, neny, 0}, {nenx, nsty, 0});
	if (!inter) return;

	bool fully = aFullyContainsB({stx, eny, 0}, {enx, sty, 0}, {nstx, neny, 0}, {nenx, nsty, 0});
	if (fully) {
		for (pt p : n->pts) {
			ans.insert(p);
		}
		return;
	}

	pt m = n->mid;
	if (pis({stx, eny, 0}, {enx, sty, 0}, m)) {
		ans.insert(m);
	}
	if (dep) {
		query(stx, enx, sty, eny, nstx, nenx, nsty, m.y, n->l, (dep + 1) % 2);
		query(stx, enx, sty, eny, nstx, nenx, m.y, neny, n->r, (dep + 1) % 2);
	} else {
		query(stx, enx, sty, eny, nstx, m.x, nsty, neny, n->l, (dep + 1) % 2);
		query(stx, enx, sty, eny, m.x, nenx, nsty, neny, n->r, (dep + 1) % 2);

	}
}

void debug(node* n) {
	if (!n) {printf("Node NULL\n"); return;}
	printf("Node, mid: (%d, %d; %d) pts: ", n->mid.x, n->mid.y, n->mid.id);
	for (pt p : n->pts) {
		printf("(%d, %d; %d), ", p.x, p.y, p.id);
	}
	printf("\n L\n");
	debug(n->l);
	printf("R\n");
	debug(n->r);
}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%d %d", &pts[i].x, &pts[i].y);
		pts[i].id = i;
	}
	build(0, N, 0, &root);
	// debug(&root);
	int Q;
	scanf("%d", &Q);
	for (int i = 0; i < Q; ++i) {
		int stx, enx, sty, eny; // inclusive
		scanf("%d %d %d %d", &stx, &enx, &sty, &eny);
		ans.clear();
		query(stx, enx, sty, eny, -MAX_R, MAX_R, -MAX_R, MAX_R, &root, 0);
		for (pt p : ans) {
			printf("%d\n", p.id);
		}
		printf("\n");
	}
}


Compiler output:
a.cc:1:1: error: expected unqualified-id before numeric constant
    1 | 1 2
      | ^
In file included from /usr/include/c++/14/bits/stl_algobase.h:62,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:2:
/usr/include/c++/14/ext/type_traits.h:164:35: error: 'constexpr const bool __gnu_cxx::__is_null_pointer' redeclared as different kind of entity
  164 |   __is_null_pointer(std::nullptr_t)
      |                                   ^
/usr/include/c++/14/ext/type_traits.h:159:5: note: previous declaration 'template<class _Type> constexpr bool __gnu_cxx::__is_null_pointer(_Type)'
  159 |     __is_null_pointer(_Type)
      |     ^~~~~~~~~~~~~~~~~
/usr/include/c++/14/ext/type_traits.h:164:26: error: 'nullptr_t' is not a member of 'std'; did you mean 'nullptr_t'?
  164 |   __is_null_pointer(std::nullptr_t)
      |                          ^~~~~~~~~
In file included from /usr/include/c++/14/cstddef:50,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:41:
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:443:29: note: 'nullptr_t' declared here
  443 |   typedef decltype(nullptr) nullptr_t;
      |                             ^~~~~~~~~
In file included from /usr/include/c++/14/bits/stl_pair.h:60,
                 from /usr/include/c++/14/bits/stl_algobase.h:64:
/usr/include/c++/14/type_traits:666:33: error: 'nullptr_t' is not a member of 'std'; did you mean 'nullptr_t'?
  666 |     struct is_null_pointer<std::nullptr_t>
      |                                 ^~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:443:29: note: 'nullptr_t' declared here
  443 |   typedef decltype(nullptr) nullptr_t;
      |                             ^~~~~~~~~
/usr/include/c++/14/type_traits:666:42: error: template argument 1 is invalid
  666 |     struct is_null_pointer<std::nullptr_t>
      |                                          ^
/usr/include/c++/14/type_traits:670:48: error: template argument 1 is invalid
  670 |     struct is_null_pointer<const std::nullptr_t>
      |                                                ^
/usr/include/c++/14/type_traits:674:51: error: template argument 1 is invalid
  674 |     struct is_null_pointer<volatile std::nullptr_t>
      |                                                   ^
/usr/include/c++/14/type_traits:678:57: error: template argument 1 is invalid
  678 |     struct is_null_pointer<const volatile std::nullptr_t>
      |                                                         ^
/usr/include/c++/14/type_traits:1429:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1429 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1429:57: error: template argument 1 is invalid
 1429 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                                         ^
/usr/include/c++/14/type_traits:1429:57: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:1438:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1438 |     : public integral_constant<std::size_t, 0> { };
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1438:46: error: template argument 1 is invalid
 1438 |     : public integral_constant<std::size_t, 0> { };
      |                                              ^
/usr/include/c++/14/type_traits:1438:46: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:1440:26: error: 'std::size_t' has not been declared
 1440 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/14/type_traits:1441:21: error: '_Size' was not declared in this scope
 1441 |     struct rank<_Tp[_Size]>
      |                     ^~~~~
/usr/include/c++/14/type_traits:1441:27: error: template argument 1 is invalid
 1441 |     struct rank<_Tp[_Size]>
      |                           ^
/usr/include/c++/14/type_traits:1442:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1442 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1442:65: error: template argument 1 is invalid
 1442 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                                                 ^
/usr/include/c++/14/type_traits:1442:65: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:1446:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1446 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1446:65: error: template argument 1 is invalid
 1446 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                                                 ^
/usr/include/c++/14/type_traits:1446:65: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:2086:26: error: 'std::size_t' has not been declared
 2086 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/14/type_traits:2087:30: error: '_Size' was not declared in this scope
 2087 |     struct remove_extent<_Tp[_Size]>
      |                              ^~~~~
/usr/include/c++/14/type_traits:2087:36: error: template argument 1 is invalid
 2087 |     struct remove_extent<_Tp[_Size]>
      |                                    ^
/usr/include/c++/14/type_traits:2099:26: error: 'std::size_t' has not been declared
 2099 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/14/type_traits:2100:35: error: '_Size' was not declared in this scope
 2100 |     struct remove_all_extents<_Tp[_Size]>
      |                                   ^~~~~
/usr/include/c++/14/type_traits:2100:41: error: template argument 1 is invalid
 2100 |     struct remove_all_extents<_Tp[_Size]>
      |                                         ^
/usr/include/c++/14/type_traits:2171:12: error: 'std::size_t' has not been declared
 2171 |   template<std::size_t _Len>
      |            ^~~
/usr/include/c++/14/type_traits:2176:30: error: '_Len' was not declared in this scope
 2176 |         unsigned char __data[_Len];
      |                              ^~~~
/usr/include/c++/14/type_traits:2194:12: error: 'std::size_t' has not been declared
 2194 |   template<std::size_t _Len, std::size_t _Align =
      |            ^~~
/usr/include/c++/14/type_traits:2194:30: error: 'std::size_t' has not been declared
 2194 |   template<std::size_t _Len, std::size_t _Align =
      |                              ^~~
/usr/include/c++/14/type_traits:2195:55: error: '_Len' was not declared in this scope
 2195 |            __alignof__(typename __aligned_storage_msa<_Len>::__type)>
      |                                                       ^~~~
/usr/include/c++/14/type_traits:2195:59: error: template argument 1 is invalid
 2195 |            __alignof__(typename __aligned_storage_msa<_Len>::__type)>
      |                                                           ^
/usr/include/c++/14/type_traits:2202:30: error: '_Len' was not declared in this scope
 2202 |         unsigned char __data[_Len];
      |                              ^~~~
/usr/include/c++/14/type_traits:2203:44: error: '_Align' was not declared in this scope
 2203 |         struct __attribute__((__aligned__((_Align)))) { } __align;
      |                                            ^~~~~~
In file included from /usr/include/c++/14/bits/stl_tempbuf.h:59,
                 from /usr/include/c++/14/bits/stl_algo.h:69,
                 from /usr/include/c++/14/algorithm:61:
/usr/include/c++/14/new:131:26: error: declaration of 'operator new' as non-function
  131 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/14/new:131:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  131 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                            ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/new:132:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  132 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/14/new:133:26: error: declaration of 'operator new []' as non-function
  133 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/14/new:133:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  133 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                              ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/new:134:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  134 |   __attribute__((__externally_visible__));
      |