Snow Boots

#include <bits/stdc++.h>
using namespace std;
 
struct Boot {
	int max_depth, max_steps, index;
};
 
int main() {
	freopen("snowboots.in", "r", stdin);
 
	int tile_num;
	int boot_num;
	cin >> tile_num >> boot_num;
 
	vector<int> tiles(tile_num);
	for (int &t : tiles) { cin >> t; }
 
	vector<Boot> boots(boot_num);
	for (int i = 0; i < boot_num; ++i) {
		cin >> boots[i].max_depth >> boots[i].max_steps;
		boots[i].index = i;
	}
	// ordenamos las botas de mayor profundidad a menor profundidad
	sort(boots.begin(), boots.end(),
	     [&](const Boot &a, const Boot &b) { return a.max_depth > b.max_depth; });
 
	vector<int> tiles_by_depth;  // lista de índices de baldosas, ordenada por profundidad de nieve
	for (int i = 1; i < tile_num - 1; i++) { tiles_by_depth.push_back(i); }
	sort(tiles_by_depth.begin(), tiles_by_depth.end(),
	     [&](int a, int b) { return tiles[a] > tiles[b]; });
 
	set<int> valid_tiles;
	for (int i = 0; i < tile_num; i++) { valid_tiles.insert(i); }
 
	// la baldosa más profunda que aún se puede atravesar con la bota en la que estamos
	int tile_at = 0;
	// el paso mínimo que una bota necesita poder dar para llegar al granero
	int needed_step = 1;
	vector<bool> can_reach(boot_num);
	for (const Boot &b : boots) {
		/*
		 * quitamos todas las baldosas que esta bota no puede atravesar
		 * y actualizamos tile_at y needed_step en consecuencia
		 */
		while (tile_at < tiles_by_depth.size() &&
		       tiles[tiles_by_depth[tile_at]] > b.max_depth) {
			auto removed = valid_tiles.find(tiles_by_depth[tile_at]);
			needed_step = max(needed_step, *next(removed) - *prev(removed));
			valid_tiles.erase(removed);
			tile_at++;
		}
		can_reach[b.index] = b.max_steps >= needed_step;
	}
 
	freopen("snowboots.out", "w", stdout);
	for (bool b : can_reach) { cout << b << '\n'; }
}

import java.io.*;
import java.util.*;
 
public class SnowBoots {
	// BeginCodeSnip{Boot Class}
	static class Boot {
		public int maxDepth;
		public int maxSteps;
		public int index;
		public Boot(int maxDepth, int maxSteps, int index) {
			this.maxDepth = maxDepth;
			this.maxSteps = maxSteps;
			this.index = index;
		}
	}
	// EndCodeSnip
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("snowboots");
 
		int tileNum = io.nextInt();
		int bootNum = io.nextInt();
 
		int[] tiles = new int[tileNum];
		for (int t = 0; t < tileNum; t++) { tiles[t] = io.nextInt(); }
 
		Boot[] boots = new Boot[bootNum];
		for (int i = 0; i < bootNum; i++) {
			boots[i] = new Boot(io.nextInt(), io.nextInt(), i);
		}
		// ordenamos las botas de mayor profundidad a menor profundidad
		Arrays.sort(boots, Comparator.comparingInt(b -> - b.maxDepth));
 
		// lista de índices de baldosas, ordenada por profundidad de nieve
		Integer[] rawTilesByDepth = new Integer[tileNum - 2];
		for (int i = 1; i < tileNum - 1; i++) { rawTilesByDepth[i - 1] = i; }
		// necesitamos la clase Integer para usar comparadores personalizados
		Arrays.sort(rawTilesByDepth, Comparator.comparingInt(t -> - tiles[t]));
 
		// casteamos los Integers de vuelta a ints por rendimiento
		int[] tilesByDepth = new int[tileNum - 2];
		for (int i = 0; i < tilesByDepth.length; i++) {
			tilesByDepth[i] = rawTilesByDepth[i];
		}
 
		TreeSet<Integer> validTiles = new TreeSet<>();
		for (int t = 0; t < tileNum; t++) { validTiles.add(t); }
 
		// la baldosa más profunda que aún se puede atravesar con la bota en la que estamos
		int tileAt = 0;
		// el paso mínimo que una bota necesita poder dar para llegar al granero
		int neededStep = 1;
		boolean[] canReach = new boolean[bootNum];
		for (Boot b : boots) {
			/*
			 * quitamos todas las baldosas que esta bota no puede atravesar
			 * y actualizamos tile_at y needed_step en consecuencia
			 */
			while (tileAt < tilesByDepth.length &&
			       tiles[tilesByDepth[tileAt]] > b.maxDepth) {
				int invalid = tilesByDepth[tileAt];
				validTiles.remove(invalid);
				neededStep = Math.max(neededStep, validTiles.ceiling(invalid) -
				                                      validTiles.floor(invalid));
				tileAt++;
			}
			canReach[b.index] = b.maxSteps >= neededStep;
		}
 
		for (boolean b : canReach) { io.println(b ? 1 : 0); }
 
		io.close();
	}
 
	// CodeSnip{Kattio}
}

from typing import NamedTuple
 
 
class Boot(NamedTuple):
	max_depth: int
	max_steps: int
	index: int
 
 
class Tile:
	def __init__(self, before: int, after: int):
		self.before = before
		self.after = after
 
 
with open("snowboots.in") as read:
	tile_num, boot_num = [int(i) for i in read.readline().split()]
	tiles = [int(i) for i in read.readline().split()]
	assert tile_num == len(tiles)
	boots = []
	for i in range(boot_num):
		max_depth, max_steps = [int(i) for i in read.readline().split()]
		boots.append(Boot(max_depth, max_steps, i))
 
# ordenamos las botas de mayor profundidad a menor profundidad
boots.sort(key=lambda b: -b.max_depth)
 
# lista de índices de baldosas, ordenada por profundidad de nieve
tiles_by_depth = [i for i in range(1, tile_num - 1)]
tiles_by_depth.sort(key=lambda t: -tiles[t])
 
valid_tiles = [Tile(i - 1, i + 1) for i in range(tile_num)]
 
# la baldosa más profunda que aún se puede atravesar con la bota en la que estamos
tile_at = 0
# el paso mínimo que una bota necesita poder dar para llegar al granero
needed_step = 1
can_reach = [False for _ in range(boot_num)]
for b in boots:
	"""
	quitamos todas las baldosas que esta bota no puede atravesar
	y actualizamos tile_at y needed_step en consecuencia
	"""
	while (
		tile_at < len(tiles_by_depth) and tiles[tiles_by_depth[tile_at]] > b.max_depth
	):
		removed = tiles_by_depth[tile_at]
 
		before = valid_tiles[removed].before
		after = valid_tiles[removed].after
 
		needed_step = max(needed_step, after - before)
 
		valid_tiles[before].after = after
		valid_tiles[after].before = before
 
		tile_at += 1
	can_reach[b.index] = b.max_steps >= needed_step
 
with open("snowboots.out", "w") as written:
	for b in can_reach:
		print(1 if b else 0, file=written)