Untitled
unknown
java
a year ago
2.2 kB
3
Indexable
Never
import java.util.Arrays; import java.util.Scanner; class Ticket implements Comparable<Ticket> { int b; int c; int max_c; public Ticket() { this.b = 0; this.c = 0; this.max_c = 0; } public Ticket(int b, int c) { this.b = b; this.c = c; this.max_c = 0; } @Override public int compareTo(Ticket other) { if (this.b < other.b) { return -1; } else if (this.b == other.b) { return Integer.compare(other.c, this.c); } else { return 1; } } } public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = scanner.nextInt(); } Ticket[] ts = new Ticket[m]; for (int i = 0; i < m; i++) { int b = scanner.nextInt(); int c = scanner.nextInt(); ts[i] = new Ticket(b, c); } Arrays.sort(ts); int max_c = 0; for (int i = 0; i < m; i++) { ts[i].max_c = Math.max(max_c, ts[i].c); if (ts[i].c > max_c) { max_c = ts[i].c; } } long res = 0; for (int i = 0; i < n; i++) { int searchValue = a[i]; int low = 0; int high = m - 1; int lastIndex = -1; while (low <= high) { int mid = (low + high) / 2; if (ts[mid].b == searchValue) { lastIndex = mid; break; } else if (ts[mid].b < searchValue) { lastIndex = mid; low = mid + 1; } else { high = mid - 1; } } if (lastIndex == -1) { res += a[i] - ts[m - 1].max_c; } else { res += a[i] - ts[lastIndex].max_c; } } System.out.println(res); } }