oj.uz

Submission #211277

# Submission time Handle Problem Language Result Execution time Memory
211277 2020-03-19T22:17:28 Z fluffypotato Just Long Neckties (JOI20_ho_t1) Java 11
0 / 100
 77 ms 10608 KB 
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.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 10608 KB Output is correct
2 Incorrect 77 ms 10332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 10608 KB Output is correct
2 Incorrect 77 ms 10332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 91.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 10608 KB Output is correct
2 Incorrect 77 ms 10332 KB Output isn't correct
3 Halted 0 ms 0 KB -