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;
for (int i = 0; i < n; i++) {
paint 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();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
114 ms |
27632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
114 ms |
27632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
114 ms |
27632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
114 ms |
27632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
