Parachutisme

Vous êtes directeur technique d'un club amateur de parachutisme dont la particularité est de se situer dans une zone très humide, avec de nombreux lacs. Votre problème est de savoir où lâcher les parachutistes pour qu'ils ne tombent pas dans un lac. Pour simplifier, on supposera que les parachutistes tombent verticalement, et que les lacs sont rectangulaires. Notez que les différents lacs peuvent se superposer.

Plus précisément, la carte de la région est carrée, quadrillée en D lignes et D colonnes (les lignes et colonnes sont numérotées de 0 à D - 1). La carte contient précisément L lacs rectangulaires. Étant donné N points de largage possibles, on vous demande de dire pour chaque point s'il se trouve au-dessus d'un lac ou non.

Voici un exemple de terrain de dimension 10 par 10 dans lequel les lacs sont coloriés en bleu et les points de largage marqués par des croix :

Limites de temps et de mémoire (Python)

  • Temps : 1 s sur une machine à 1 GHz.
  • Mémoire : 64 000 ko.

Contraintes

  • 1 <= D <= 1 000, où D est le nombre de lignes et de colonnes.
  • 1 <= L <= 2 000, où L est le nombre de lacs.
  • 1 <= N <= 100 000, où N est le nombre de points de largage envisageables.

Entrée

  • La première ligne de l'entrée contient trois entiers séparés par des espaces : les dimensions D de la carte, le nombre L de lacs, et le nombre N de points de largage.
  • Chacune des L lignes suivantes contient quatre entiers séparés par des espaces, décrivant un lac rectangulaire : la ligne et la colonne du coin en haut à gauche du lac, puis la ligne et la colonne du coin tout en bas à droite du lac.
  • Chacune des N lignes suivantes contient deux entiers séparés par un espace : la ligne et la colonne d'un point de largage.

Sortie

La sortie doit être composée de N lignes. La i-ème ligne doit contenir l'entier 1 si le i-ème point de larguage se situe au-dessus d'un lac, et l'entier 0 sinon.

Exemple

entrée :

10 3 8
2 5 5 8
4 2 8 5
0 0 2 1
7 0
1 8
8 8
7 3
5 1
0 0
3 4
5 5

sortie :

0
0
0
1
0
1
0
1

Commentaires

Cet exemple correspond à la carte donnée précédemment.


Source : https://www.france-ioi.org/ Créé par : Lucien Pech.