Tower Defense
Source: aizu

Tower Defense
Problem Statement

There are $M+1$ cells labeled from $0$ to $M$ arranged in sequence. Cell $0$ contains a base, and cell $M$ contains a monster with health $H$. There are $N$ soldiers deployed near the cells. The attack range of soldier $i$ is from cell $L_i$ to $R_i$ (i.e., cells $L_i, L_{i+1}, ..., R_i$).

Each turn, both the monster and the soldiers perform the following actions in order (first the monster, then the soldiers):

Monster: If the monster’s health $1$ is or more and it is not in cell $0$, it moves one cell closer to the base (i.e., it moves to the cell with a number $1$ smaller).
Soldiers: Any soldier whose attack range includes the cell where the monster is currently located attacks the monster and reduces its health by $1$.

If the monster’s health drops to $0$ or below before it reaches cell $0$, the monster dies in that cell, the defense is successful, and the game ends. If the monster reaches cell $0$ without its health dropping to $0$ or below, the defense fails and the game ends.

Determine whether the defense will succeed, and if so, find the number of the cell where the monster will die.

Input

The input consists of a single test case of the following format.

$N$ $M$ $H$
$L_1$ $R_1$
$\vdots$
$L_N$ $R_N$


The first line contains three integers, $N$, $M$, and $H$, representing the number of soldiers, the number of cells, and the monster’s health, respectively. $N$ is between $1$ and $100,000$ (both inclusive). $M$ is between $2$ and $10^6$ (both inclusive). $H$ is between $1$ and $10^{11}$ (both inclusive).

The next $N$ lines each contain two integers, $L_i$ and , $R_i$ which represent the attack range interval of the $i$-th soldier. Both $L_i$ and $R_i$ are between $1$ and $M-1$ (both inclusive). It is guaranteed that $L_i$ is less than or equal to $R_i$.

Output

Output a single integer, the number of the cell where the monster will die if the defense is successful; otherwise, output $-1$.

Sample Input 1
2 5 3
2 4
3 4

Sample Output 1
3

Sample Input 2
4 5 10
1 2
2 4
4 4
3 4

Sample Output 2
-1


C++ solution:
// AOJ #3637
// Tower Defense 2025.1.24

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N, M;
    ll H;
    cin >> N >> M >> H;
    
    vector<int> diff(M + 2, 0);
    
    for(int i=0; i<N; i++){
        int Li, Ri;
        cin >> Li >> Ri;
        diff[Li]++;
        if(Ri+1 <= M) diff[Ri+1]--;
    }
    
    vector<int> cnt(M+1, 0);
    cnt[0] = 0;
    for(int c=1; c<=M; c++){
        cnt[c] = cnt[c-1] + diff[c];
    }
    
    for(int c = M-1; c >=0; c--){
        H -= cnt[c];
        if(H <= 0 && c > 0){
            cout << c << '\n';
            return 0;
        }
    }
    cout << "-1\n";
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	scanner.Scan()
	N, _ := strconv.Atoi(scanner.Text())
	scanner.Scan()
	M, _ := strconv.Atoi(scanner.Text())
	scanner.Scan()
	H, _ := strconv.ParseInt(scanner.Text(), 10, 64)

	diff := make([]int, M+2)
	for i := 0; i < N; i++ {
		scanner.Scan()
		Li, _ := strconv.Atoi(scanner.Text())
		scanner.Scan()
		Ri, _ := strconv.Atoi(scanner.Text())
		diff[Li]++
		if Ri+1 <= M {
			diff[Ri+1]--
		}
	}

	cnt := make([]int64, M+1)
	cnt[0] = 0
	for c := 1; c <= M; c++ {
		cnt[c] = cnt[c-1] + int64(diff[c])
	}

	for c := M; c >= 1; c-- {
		H -= cnt[c]
		if H <= 0 {
			fmt.Println(c)
			return
		}
	}
	fmt.Println(-1)
}

Java solution:
import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        long H = Long.parseLong(st.nextToken());

        int[] diff = new int[M + 2]; // Using 1-based to M

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int Li = Integer.parseInt(st.nextToken());
            int Ri = Integer.parseInt(st.nextToken());
            diff[Li]++;
            if (Ri + 1 <= M) {
                diff[Ri + 1]--;
            }
        }

        int[] cnt = new int[M + 1];
        cnt[0] = 0;
        for (int c = 1; c <= M; c++) {
            cnt[c] = cnt[c - 1] + diff[c];
        }

        for (int c = M - 1; c >= 0; c--) {
            H -= cnt[c];
            if (H <= 0 && c > 0) {
                System.out.println(c);
                return;
            }
        }
        System.out.println(-1);
    }
}

JavaScript solution:
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let inputLines = [];
let currentLine = 0;

rl.on('line', (line) => {
    inputLines.push(line);
});

rl.on('close', () => {
    solve();
});

function solve() {
    const firstLine = inputLines[0].split(' ').map(Number);
    const N = firstLine[0];
    const M = firstLine[1];
    let H = BigInt(firstLine[2]);

    const diff = new Array(M + 2).fill(0);

    for (let i = 1; i <= N; i++) {
        const [Li, Ri] = inputLines[i].split(' ').map(Number);
        diff[Li]++;
        if (Ri + 1 <= M) {
            diff[Ri + 1]--;
        }
    }

    const cnt = new Array(M + 1).fill(0);
    cnt[0] = 0;
    for (let c = 1; c <= M; c++) {
        cnt[c] = cnt[c - 1] + diff[c];
    }

    for (let c = M; c >= 1; c--) {
        H -= BigInt(cnt[c]);
        if (H <= 0 && c > 0) {
            console.log(c.toString());
            return;
        }
    }
    console.log("-1");
}

Python solution:
import sys

def solve():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    H = int(input[ptr])
    ptr += 1
    
    diff = [0] * (M + 2)
    
    for _ in range(N):
        Li = int(input[ptr])
        ptr += 1
        Ri = int(input[ptr])
        ptr += 1
        diff[Li] += 1
        if Ri + 1 <= M:
            diff[Ri + 1] -= 1
    
    cnt = [0] * (M + 1)
    cnt[0] = 0
    for c in range(1, M + 1):
        cnt[c] = cnt[c - 1] + diff[c]
    
    for c in range(M - 1, -1, -1):
        H -= cnt[c]
        if H <= 0 and c > 0:
            print(c)
            return
    print(-1)

solve()

Ruby solution:
def main
  # Read input values
  n, m, h = gets.split.map(&:to_i)
  
  # Initialize difference array with +2 to handle R+1 safely
  diff = Array.new(m + 2, 0)
  
  # Process each soldier's attack range
  n.times do
    l, r = gets.split.map(&:to_i)
    diff[l] += 1
    diff[r + 1] -= 1 if r + 1 <= m
  end
  
  # Compute prefix sum to get attack counts per cell
  cnt = Array.new(m + 1, 0)
  (1..m).each do |c|
    cnt[c] = cnt[c - 1] + diff[c]
  end
  
  # Simulate monster movement and attacks
  current_cell = m - 1
  while current_cell >= 0
    h -= cnt[current_cell]
    if h <= 0 && current_cell > 0
      puts current_cell
      return
    end
    current_cell -= 1
  end
  
  # If monster reaches base
  puts -1
end

main