Submission #1254647

#TimeUsernameProblemLanguageResultExecution timeMemory
1254647vibhasAdvertisement 2 (JOI23_ho_t2)Java
100 / 100
790 ms147040 KiB
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        List<Resident> residents = new ArrayList<>();
        for(int i = 0; i < n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            Resident r = new Resident(e-x, e+x);
            residents.add(r);
        }
        br.close();
        Collections.sort(residents);
        Stack<Resident> stack = new Stack<>();
        for(Resident r : residents) {
            while(!stack.isEmpty() && stack.peek().add <= r.add){
                stack.pop();
            }
            stack.push(r);
        }
        System.out.println(stack.size());
    }
    static class Resident implements Comparable<Resident> {
        int sub;
        int add;
        public Resident (int sub, int add){
            this.sub = sub;
            this.add = add;
        }
        public int compareTo (Resident r){
            if(this.sub == r.sub){
                return this.add-r.add;
            }
            return this.sub-r.sub;
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...