Submission #227513

#	Time	Username	Problem	Language	Result	Execution time	Memory
227513		Bruteforceman	Sky Walking (IOI19_walk)	Java	10 / 100	4665 ms	207108 KiB

walk

import java.math.*;
import java.util.*;
class walk {
  class Pair implements Comparator <Pair> {
    int first, second;
    Pair () {}
    Pair (int first, int second) {
      this.first = first; this.second = second;
    }
    public int compare(Pair a, Pair b) {
      if(a.first == b.first) return a.second - b.second;
      return a.first - b.first;
    }
  }
  class Node implements Comparator <Node> {
    long dist;
    int pos, line;
    Node () {}
    Node (long dist, int pos, int line) {
      this.dist = dist; this.pos = pos; this.line = line;
    }
    public int compare(Node a, Node b) {
      if(a.dist != b.dist) return Long.compare(a.dist, b.dist);
      if(a.pos != b.pos) return a.pos - b.pos;
      return a.line - b.line;
    }
  }
	public long min_distance(int[] x, int[] h, int[] l, int[] r, int[] y, int f, int g) {
    int n = x.length;
    int m = y.length;
    TreeSet <Pair> [] s = new TreeSet [n];
    ArrayList <Pair> ls = new ArrayList <> ();
    TreeSet <Integer> [] ch = new TreeSet [m];

    for(int i = 0; i < n; i++) {
      s[i] = new TreeSet <> (new Pair());
      ls.add(new Pair(-h[i], -i - 1));
    }
    for(int i = 0; i < m; i++) {
      ls.add(new Pair(-y[i], i));
    }
    Collections.sort(ls, new Pair());
    
    TreeSet <Integer> aux = new TreeSet <> ();
    for(Pair i : ls) {
      if(i.second < 0) {
        aux.add(-i.second - 1);
      } else {
        ch[i.second] = new TreeSet <> 
          (aux.subSet(l[i.second], r[i.second] + 1));
        for(int j : ch[i.second]) {
          s[j].add(new Pair(-i.first, i.second));
        }
      }
    }
    s[f].add(new Pair(0, m));
    s[g].add(new Pair(0, m + 1));

    TreeMap <Pair, Long> dist = new TreeMap <> (new Pair());
    TreeSet <Node> q = new TreeSet <> (new Node());
    q.add(new Node(0L, f, m));
    dist.put(new Pair(f, m), 0L);
    while(!q.isEmpty()) {
      int pos = q.first().pos;
      int line = q.first().line;
      long current = q.first().dist;
      q.remove(new Node(current, pos, line));
      int high = (line >= m) ? 0 : y[line];
      if(dist.get(new Pair(pos, line)) != current) continue;

      ArrayList <Pair> can = new ArrayList <> ();
      if(line < m) {
        Integer a = ch[line].lower(pos);
        Integer b = ch[line].higher(pos);
        if(a != null) can.add(new Pair(a, line));
        if(b != null) can.add(new Pair(b, line)); 
      }
      Pair a = s[pos].lower(new Pair(high, line));
      Pair b = s[pos].higher(new Pair(high, line));
      if(a != null) {
        can.add(new Pair(pos, a.second));
      }
      if(b != null) {
        can.add(new Pair(pos, b.second));
      }
      for(Pair i : can) {
        int nxtH = (i.second >= m) ? 0 : y[i.second];
        long d = current + Math.abs(x[pos] - x[i.first]) + 
          Math.abs(high - nxtH);
        if(dist.get(i) == null || dist.get(i) > d) {
          dist.put(new Pair(i.first, i.second), d);
          q.add(new Node(d, i.first, i.second));
        }
      }
    }
		return dist.get(new Pair(g, m + 1)) == null ? -1 : dist.get(new Pair(g, m + 1));
	}
}

Compilation message (stderr)

Note: walk.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43