제출 #281995

#제출 시각아이디문제언어결과실행 시간메모리
281995FlashGamezzzArt Exhibition (JOI18_art)Java
50 / 100
1129 ms135980 KiB
import java.io.*;
import java.util.*;

public class art {
	static int n;
	static long[] max = new long[1100000], upd = new long[1100000];
	static void upd(int l, int u, long d) {
		upd(0, 0, n-1, l, u, d);
	}
	static void upd(int i, int s, int e, int l, int u, long d) {
		if (upd[i] != 0) { 
			max[i] += upd[i];
			if (s != e) { 
				upd[i * 2 + 1] += upd[i]; 
				upd[i * 2 + 2] += upd[i]; 
			}
			upd[i] = 0;
		} 
		if (s > e || s > u || e < l) {
			return; 
		}
		if (s >= l && e <= u) { 
			max[i] += d;
			if (s != e) { 
				upd[i * 2 + 1] += d; 
				upd[i * 2 + 2] += d; 
			} 
			return; 
		}  
		upd(i * 2 + 1, s, (s + e)/2, l, u, d); 
		upd(i * 2 + 2, (s + e)/2 + 1, e, l, u, d); 
		max[i] = Long.max(max[i * 2 + 1], max[i * 2 + 2]);
	}
	static long max(int l, int u) {
		return max(0, 0, n-1, l, u);
	}
	static long max(int i, int s, int e, int l, int u) {
		if (upd[i] != 0) { 
			max[i] += upd[i];
			if (s != e) { 
				upd[i * 2 + 1] += upd[i]; 
				upd[i * 2 + 2] += upd[i]; 
			}
			upd[i] = 0;
		}
		if (s > e || s > u || e < l) {
			return Long.MIN_VALUE; 
		}
		if (s >= l && e <= u) { 
			return max[i]; 
		}
		return Long.max(max(2*i+1, s, (s+e)/2, l, u), max(2*i+2, (s+e)/2+1, e, l, u)); 
	}
	static class paint implements Comparable<paint>{
		int a;
		long s;
		paint (int x, long y) {
			a = x;
			s = y;
		}
		public int compareTo(paint o) {
			if (s < o.s) {
				return -1;
			}
			if (s == o.s) {
				return 0;
			}
			return 1;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		n = Integer.parseInt(br.readLine());
		PriorityQueue<paint> pq = new PriorityQueue<paint>();
		for (int i = 0; i < n; i++) {
			String[] line = br.readLine().split(" ");
			pq.add(new paint(Integer.parseInt(line[1]), Long.parseLong(line[0])));
		}
		long size = pq.peek().s;
		long ans = 0;
		upd(0, 0, pq.poll().a);
		for (int i = 1; i < n; i++) {
			paint c = pq.poll();
			upd(0, i-1, size-c.s);
			upd(0, i, c.a);
			ans = Long.max(ans, max(0, i));
			size = c.s;
		}
		pw.println(ans);
		pw.close();
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...