1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class sia {
  public static void main(String[] args) {
    // reading input
    Scanner scanner = new Scanner(System.in);

    long fieldCount = scanner.nextLong();
    long harvestCount = scanner.nextLong();

    long[] speeds = new long[(int) fieldCount];
    for (int i = 0; i < fieldCount; i++) {
      speeds[i] = scanner.nextLong();
    }

    // preparing
    Arrays.sort(speeds);

    long[] speedIntegrations = new long[(int) fieldCount + 1];
    speedIntegrations[0] = 0;
    for (int i = 1; i < fieldCount + 1; i++) {
      speedIntegrations[i] = speedIntegrations[i - 1] + speeds[i - 1];
    }

    LinkedList<long[]> positionDayHeights = new LinkedList<>();
    positionDayHeights.add(new long[] { 0L, 0L, 0L });

    // solving
    for (int i = 0; i < harvestCount; i++) {
      long day = scanner.nextLong();
      long height = scanner.nextLong();

      long harvested = 0;
      long sawPosition = fieldCount;

      while (!positionDayHeights.isEmpty()) {
        long[] last = positionDayHeights.getLast();
        long position = last[0];
        long pastDay = last[1];
        long pastHeight = last[2];
        long duration = day - pastDay;
        long speed = speeds[(int) position];
        long currentHeight = pastHeight + duration * speed;
        if (height <= currentHeight) {
          long harvestedPerDay = speedIntegrations[(int) sawPosition]
              - speedIntegrations[(int) position];
          harvested += harvestedPerDay * duration;
          harvested -= (sawPosition - position) * (height - pastHeight);
          sawPosition = position;
          positionDayHeights.removeLast();
        } else {
          break;
        }
      }
      if (!positionDayHeights.isEmpty()) {
        long[] last = positionDayHeights.getLast();
        long badPosition = last[0];
        long goodPosition = sawPosition;
        long pastDay = last[1];
        long pastHeight = last[2];
        while (goodPosition - badPosition > 1) {
          long bisect = (goodPosition + badPosition) / 2;
          long duration = (day - pastDay);
          long speed = speeds[(int) bisect];
          long currentHeight = pastHeight + duration * speed;
          if (height < currentHeight) {
            long harvestedPerDay = speedIntegrations[(int) goodPosition]
                - speedIntegrations[(int) bisect];
            harvested += harvestedPerDay * duration;
            harvested -= (goodPosition - bisect) * (height - pastHeight);
            goodPosition = bisect;
          } else {
            badPosition = bisect;
          }
        }
        if (goodPosition != fieldCount) {
          positionDayHeights.add(new long[] { goodPosition, day, height });
        }
      } else {
        positionDayHeights.add(new long[] { 0, day, height });
      }
      System.out.println(harvested);
    }
    scanner.close();
  }
}