# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
281985 | FlashGamezzz | Art Exhibition (JOI18_art) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
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 art implements Comparable<art>{
int a;
long s;
art (int x, long y) {
a = x;
s = y;
}
public int compareTo(art 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<art> pq = new PriorityQueue<art>();
for (int i = 0; i < n; i++) {
String[] line = br.readLine().split(" ");
pq.add(new art(Integer.parseInt(line[1]), Long.parseLong(line[0])));
}
long size = pq.peek().s;
long ans = 0;
for (int i = 0; i < n; i++) {
art c = pq.poll();
upd(0, i, size-c.s);
upd(0, i, c.a);
ans = Long.max(ans, max(0, i));
size = c.s;
}
pw.println(ans);
pw.close();
}