gt22

Untitled

Sep 20th, 2018
238
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.24 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.LinkedList;
  5. import java.util.Queue;
  6.  
  7. public class O1987 {
  8.  
  9.     static class Segment {
  10.  
  11.         int id, start, end;
  12.         Queue<Segment> children = new LinkedList<>();
  13.         Segment parent;
  14.  
  15.         Segment(int id, int start, int end, Segment parent) {
  16.             this.id = id;
  17.             this.start = start;
  18.             this.end = end;
  19.             this.parent = parent;
  20.         }
  21.  
  22.         boolean covers(int point) {
  23.             return start <= point && point <= end;
  24.         }
  25.  
  26.         @Override
  27.         public String toString() {
  28.             return start + "#" + end + "(" + children.size() + ")";
  29.         }
  30.     }
  31.  
  32.     public static void main(String[] args) throws IOException {
  33.         BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
  34.         int n = Integer.parseInt(r.readLine());
  35.         Segment root = new Segment(-1, 0, Integer.MAX_VALUE, null);
  36.         Segment cur = root;
  37.         for (int i = 0; i < n; i++) {
  38.             String[] s = r.readLine().split(" ");
  39.             int start = Integer.parseInt(s[0]), end = Integer.parseInt(s[1]);
  40.             while(start > cur.end) {
  41.                 cur = cur.parent;
  42.             }
  43.             cur.children.offer(cur = new Segment(i + 1, start, end, cur));
  44.         }
  45.         int c = Integer.parseInt(r.readLine());
  46.         cur = root;
  47.         for (int i = 0; i < c; i++) {
  48.             int point = Integer.parseInt(r.readLine());
  49.             while(!cur.covers(point)) {
  50.                 cur = cur.parent;
  51.                 // Current segment can only be leftmost, otherwise it would be removed earlier
  52.                 cur.children.remove();
  53.             }
  54.             while(!cur.children.isEmpty()) {
  55.                 Segment child = cur.children.element();
  56.                 if(!child.covers(point)) {
  57.                     if(child.end < point) {
  58.                         cur.children.remove();
  59.                     } else {
  60.                         break;
  61.                     }
  62.                 } else {
  63.                     cur = cur.children.element();
  64.                 }
  65.             }
  66.             System.out.println(cur.id);
  67.         }
  68.     }
  69.  
  70.  
  71. }
Advertisement
Add Comment
Please, Sign In to add comment