Submission #211277

#	Time	Username	Problem	Language	Result	Execution time	Memory
211277		fluffypotato	Just Long Neckties (JOI20_ho_t1)	Java	0 / 100	77 ms	10608 KiB

ho_t1

import java.util.*;
import java.io.*;

public class ho_t1 {
    public static void main(String[] args) throws IOException{
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new PrintStream(System.out));
        int n=Integer.parseInt(f.readLine());
        pair[]arr1=new pair[n+1];
        StringTokenizer st=new StringTokenizer(f.readLine());
        for(int i=0;i<=n;i++){
            arr1[i]=new pair(Integer.parseInt(st.nextToken()),i);
        }
        st=new StringTokenizer(f.readLine());
        pair[]arr2=new pair[n];
        for(int i=0;i<n;i++){
            arr2[i]=new pair(Integer.parseInt(st.nextToken()),i);
        }
        int ans[]=new int[n+1];
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        int[]ans1=new int[n];
        int[]ans2=new int[n];
        int[]prefix1=new int[n];
        int[]prefix2=new int[n];
        for(int i=0;i<n;i++){
            ans1[i]=Math.max(0,arr1[i].num-arr2[i].num);
            prefix1[i]=i==0?ans1[i]:Math.max(prefix1[i-1],ans1[i]);
            ans2[i]=Math.max(0,arr1[i+1].num-arr2[i].num);
        }
        for(int i=n-1;i>=0;i--){
            prefix2[i]=i==n-1?ans2[i]:Math.max(ans2[i],prefix2[i+1]);
        }
        for(int i=0;i<=n;i++){
            if(i==0){
                ans[arr1[i].idx]=prefix2[i+1];
            }
            if(i==n){
                ans[arr1[i].idx]=prefix1[i-1];
            }
            if(i>0 && i<n){
                ans[arr1[i].idx]=Math.max(prefix1[i-1],prefix2[i]);
            }
        }
        out.print(ans[0]);
        for(int i=1;i<=n;i++){
            out.print(" "+ans[i]);
        }
        f.close();
        out.close();
    }
}
class pair implements Comparable <pair>{
    int num;
    int idx;

    public int compareTo(pair other){
        return num- other.num;
    }


    pair(int a, int b)
    {
        num=a;
        idx=b;
    }
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 8
• Subtask 3: 0 / 91