fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5.     public static int[] solve(int L, int n, int[] pos) {
  6.         int[] ans = new int[n];
  7.  
  8.         TreeSet<Integer> s = new TreeSet<>();
  9.         s.add(0);
  10.         s.add(L);
  11.  
  12.         TreeMap<Integer, Integer> seg = new TreeMap<>();
  13.         seg.put(L, 1);
  14.  
  15.         for (int i = 0; i < n; i++) {
  16.             int p = pos[i];
  17.  
  18.             int r = s.higher(p);
  19.             int l = s.lower(p);
  20.  
  21.             int old = r - l;
  22.             int cnt = seg.get(old);
  23.             if (cnt == 1) seg.remove(old);
  24.             else seg.put(old, cnt - 1);
  25.  
  26.             int a = p - l;
  27.             int b = r - p;
  28.  
  29.             seg.put(a, seg.getOrDefault(a, 0) + 1);
  30.             seg.put(b, seg.getOrDefault(b, 0) + 1);
  31.  
  32.             s.add(p);
  33.  
  34.             ans[i] = seg.lastKey();
  35.         }
  36.  
  37.         return ans;
  38.     }
  39.  
  40.     public static void main(String[] args) {
  41.         Scanner sc = new Scanner(System.in);
  42.  
  43.         int L = sc.nextInt();
  44.         int n = sc.nextInt();
  45.         int[] pos = new int[n];
  46.         for (int i = 0; i < n; i++) {
  47.             pos[i] = sc.nextInt();
  48.         }
  49.  
  50.         int[] res = solve(L, n, pos);
  51.  
  52.         for (int x : res) {
  53.             System.out.print(x + " ");
  54.         }
  55.         System.out.println();
  56.     }
  57. }
Success #stdin #stdout 0.17s 59180KB
comments (?)
stdin
copy 
10 5 
1 2 3 4 5
stdout
copy 
9 8 7 6 5
https://ideone.com/e02bUm
language:
Java (12.0.1)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!