Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Scanner;
- public class Alarm {
- public static class Pair {
- long x;
- long y;
- Pair(long x, long y) {
- this.x = x;
- this.y = y;
- }
- }
- static void merge(Pair arr[], int l, int m, int r)
- {
- int n1 = m - l + 1;
- int n2 = r - m;
- Pair L[] = new Pair [n1];
- Pair R[] = new Pair [n2];
- for (int i=0; i<n1; ++i)
- L[i] = arr[l + i];
- for (int j=0; j<n2; ++j)
- R[j] = arr[m + 1 + j];
- int i = 0, j = 0;
- int k = l;
- while (i < n1 && j < n2)
- {
- if (L[i].y < R[j].y || (L[i].y == R[j].y && L[i].x < R[j].x))
- {
- arr[k] = L[i];
- i++;
- }
- else
- {
- arr[k] = R[j];
- j++;
- }
- k++;
- }
- while (i < n1)
- {
- arr[k] = L[i];
- i++;
- k++;
- }
- while (j < n2)
- {
- arr[k] = R[j];
- j++;
- k++;
- }
- }
- static void sort(Pair arr[], int l, int r)
- {
- if (l < r)
- {
- int m = (l+r)/2;
- sort(arr, l, m);
- sort(arr , m+1, r);
- merge(arr, l, m, r);
- }
- }
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- int n = in.nextInt();
- long x = in.nextLong();
- long k = in.nextLong();
- Pair numbers[] = new Pair [n];
- for (int i = 0; i < n; i++)
- {
- long input = in.nextLong();
- Pair pair = new Pair(input, input % x);
- numbers[i] = pair;
- }
- sort(numbers, 0, numbers.length - 1);
- long lo = 0;
- long hi = (long)Math.pow(10, 18);
- while (lo < hi) {
- long mid = (lo + hi) / 2;
- long col = 0;
- long last = -1;
- for (Pair b : numbers) {
- if (b.y != last && mid >=b.x) {
- col += (mid - b.x) / x + 1;
- last = b.y;
- }
- }
- if (k <= col)
- hi = mid;
- else
- lo = mid + 1;
- }
- System.out.println(lo);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement