oj.uz

Submission #366056

# Submission time Handle Problem Language Result Execution time Memory
366056 2021-02-12T21:57:59 Z dapig Global Warming (CEOI18_glo) Java 11
0 / 100
 451 ms 28576 KB 
//package lis;

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

class glo {

	public static void main(String[] args) throws IOException {

		glo obj = new glo();

		obj.doStuff();

	}
	
	int binsearch(int val) {
		int l = 0, r = this.r;
		while (l < r) {
			int m = (l+r)/2;
			if (val < maxlist[m]) {
				if (val > maxlist[m+1]) return m;
				l = m+1;
			} else r=m;
		}
		return l;
	}
	
	int[] maxlist; int r = 0;
	int[][] changes;
	void create() {
		maxlist = new int[nums.length+1];
		changes = new int[nums.length][2];
		Arrays.fill(maxlist, Integer.MIN_VALUE);
		maxlist[0] = Integer.MAX_VALUE;
		for (int i = nums.length-1; i >= 0; i--) {
			int pos = binsearch(nums[i]);
			pos++; r = Math.max(r, pos);
			changes[i] = new int[] {pos, maxlist[pos]};
			maxlist[pos] = nums[i];
		}
	}
	
	int binsearch2(int val) {
		int l = 0, r = this.r2;
		while (l < r) {
			int m = (l+r)/2;
			if (val > lis[m]) {
				if (val < lis[m+1]) return m;
				l=m+1;
			} else r=m;
		}
		return l;
	}
	
	int find(int val) {
		int l = 1, r = maxlist.length-1;
		while (l<r) {
			int m = (l+r)/2;
			if (val >= maxlist[m]) {
				if (val < maxlist[m-1]) return m;
				r = m;
			} else l = m+1;
		}
		return l;
	}
	
	int[] lis; int r2 = 0;
	int process() {
		int ans = r;
		lis = new int[changes.length+1];
		Arrays.fill(lis, Integer.MAX_VALUE);
		lis[0] = Integer.MIN_VALUE;
		for (int i = 0; i < changes.length-1; i++) {
			maxlist[changes[i][0]] = changes[i][1];
			int pos = binsearch2(nums[i]);
			pos++; r2 = Math.max(r2, pos);
			lis[pos] = nums[i];
			int res = find(nums[i]-max)-1;
			ans = Math.max(ans, r2+res);
		}
		return ans;
	}

	int[] nums; int max;
	private void doStuff() throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		max = Integer.parseInt(st.nextToken());
		nums = new int[n];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < nums.length; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		br.close();
		
		create();
		System.out.println(process());
		
	}

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 8448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 8448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 8448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 424 ms 28456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 332 ms 16728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 21944 KB Output is correct
2 Correct 359 ms 22080 KB Output is correct
3 Correct 451 ms 28576 KB Output is correct
4 Incorrect 400 ms 27648 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 8448 KB Output isn't correct
2 Halted 0 ms 0 KB -