Submission #366056

#	Time	Username	Problem	Language	Result	Execution time	Memory
366056		dapig	Global Warming (CEOI18_glo)	Java	0 / 100	451 ms	28576 KiB

glo

//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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25