fork(1) download
copy 
  1. import java.io.*;
  2. import java.util.Locale;
  3. import java.util.StringTokenizer;
  4.  
  5. public class TaskB {
  6.     private final InputReader reader;
  7.     private final OutputWriter writer;
  8.  
  9.     public TaskB(InputReader reader, OutputWriter writer) {
  10.         this.reader = reader;
  11.         this.writer = writer;
  12.     }
  13.  
  14.     public static void main(String[] args) {
  15.         InputReader reader = new InputReader(System.in);
  16.         OutputWriter writer = new OutputWriter(System.out);
  17.         new TaskB(reader, writer).run();
  18.         writer.writer.flush();
  19.     }
  20.  
  21.     public void run() {
  22.         int n = reader.nextInt();
  23.         int[] A = new int[n + 2];
  24.         for (int i = 1; i <= n; i++)
  25.             A[i] = reader.nextInt();
  26.         A[0] = A[n + 1] = 0;
  27.         int[] S = new int[n + 2];
  28.         int pt = 0;
  29.         S[pt++] = 0;
  30.         int[] L = new int[n + 2];
  31.         int[] R = new int[n + 2];
  32.         for (int i = 1; i <= n; i++) {
  33.             while (A[S[pt - 1]] >= A[i])
  34.                 --pt;
  35.             L[i] = S[pt - 1];
  36.             S[pt++] = i;
  37.         }
  38.         pt = 0;
  39.         S[pt++] = n + 1;
  40.         for (int i = n; i >= 1; i--) {
  41.             while (A[S[pt - 1]] >= A[i])
  42.                 --pt;
  43.             R[i] = S[pt - 1];
  44.             S[pt++] = i;
  45.         }
  46.         int[] ans = new int[n + 1];
  47.         for (int i = 1; i <= n; i++) {
  48.             int len = R[i] - L[i] - 1;
  49.             ans[len] = Math.max(ans[len], A[i]);
  50.         }
  51.         for (int i = n - 1; i >= 1; i--)
  52.             ans[i] = Math.max(ans[i], ans[i + 1]);
  53.         for (int i = 1; i <= n; i++)
  54.             writer.printf("%d%c", ans[i], i == n ? '\n' : ' ');
  55.     }
  56.  
  57.  
  58.     static class InputReader {
  59.         public BufferedReader reader;
  60.         public StringTokenizer tokenizer;
  61.  
  62.         public InputReader(InputStream stream) {
  63.             reader = new BufferedReader(new InputStreamReader(stream), 32768);
  64.             tokenizer = null;
  65.         }
  66.  
  67.         public String next() {
  68.             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  69.                 try {
  70.                     tokenizer = new StringTokenizer(reader.readLine());
  71.                 } catch (IOException e) {
  72.                     throw new RuntimeException(e);
  73.                 }
  74.             }
  75.             return tokenizer.nextToken();
  76.         }
  77.  
  78.         public int nextInt() {
  79.             return Integer.parseInt(next());
  80.         }
  81.  
  82.         public double nextDouble() {
  83.             return Double.parseDouble(next());
  84.         }
  85.  
  86.         public long nextLong() {
  87.             return Long.parseLong(next());
  88.         }
  89.     }
  90.  
  91.     static class OutputWriter {
  92.         public PrintWriter writer;
  93.  
  94.         OutputWriter(OutputStream stream) {
  95.             writer = new PrintWriter(stream);
  96.         }
  97.  
  98.         public void printf(String format, Object... args) {
  99.             writer.print(String.format(Locale.ENGLISH, format, args));
  100.         }
  101.     }
  102. }
  103.  
  104.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:5: error: class TaskB is public, should be declared in a file named TaskB.java
public class TaskB {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/EDr7bG
language:
Java (12.0.1)
created:
8 years 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!