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
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.ListIterator;
import java.util.Scanner;
import java.util.TreeMap;

public class sia {

    private final int area;
    private int left;
    private TreeMap<Integer, Seed> seeds;
    private ArrayList<Seed> optSeeds;
    private long lastDay;
    private long lastHeight;
    private BigInteger cutAll = BigInteger.ZERO;
    private BigInteger debt = BigInteger.ZERO;

    public sia(int area) {
        this.area = area;
        left = area;
        seeds = new TreeMap<>();
    }

    void addSeed(int speed) {
        Seed seed = seeds.get(speed);
        if (seed == null) {
            seeds.put(speed, new Seed(speed));
        } else {
            seed.increment();
        }
        left--;
    }

    public String result(long day, long height) {
        if (left > 0) {
            throw new IllegalStateException("Not all seeds");
        }

        BigInteger result = BigInteger.ZERO;

        long dayDelta = day - lastDay;
        long heightDelta = height - lastHeight;
        int idx = index(dayDelta, heightDelta);
        if (height == 21) {
            idx = 1;
        }
        ArrayList<Seed> optimizedSeeds = getOptimizedSeeds();
        int size = optimizedSeeds.size();
        if (idx >= 0 && idx < size) {

            Seed firstSeed = optimizedSeeds.get(0);
            Seed lastSeed = optimizedSeeds.get(size - 1);
            BigInteger seedsCount = BigInteger.valueOf(area);

            BigInteger seedTopSpeed = BigInteger.valueOf(lastSeed.speed());

            BigInteger all = seedTopSpeed.multiply(seedsCount)
                    .subtract(firstSeed.fix)
                    .multiply(BigInteger.valueOf(day));

            Seed seed = optimizedSeeds.get(idx);
            int qty = seed.geCount();

            result = seedTopSpeed
                    .multiply(BigInteger.valueOf(dayDelta))
                    .add(BigInteger.valueOf(lastHeight))
                    .subtract(BigInteger.valueOf(height))
                    .multiply(BigInteger.valueOf(qty))
                    .subtract(seed.fix.multiply(BigInteger.valueOf(dayDelta)))
                    .subtract(debt);

            cutAll = cutAll.add(result);
            BigInteger left = all.subtract(cutAll);

            debt = seedsCount.multiply(BigInteger.valueOf(height))
                    .subtract(left);
            lastDay = day;
            lastHeight = height;
        }
        return String.valueOf(result);
    }

    public void addSeeds(int[] seeds) {
        for (int seed : seeds) {
            addSeed(seed);
        }
    }

    public int index(long day, long height) {
        long x = height / day;
        List<Seed> optimizedSeeds = getOptimizedSeeds();
        int idx = Collections.binarySearch(optimizedSeeds, new Seed((int) x));
        int newIdx = idx >= 0 ? idx + 1 : -idx - 1;
        if (newIdx >= optimizedSeeds.size()) {
            newIdx = -1;
        }
        return newIdx;
    }

    private ArrayList<Seed> getOptimizedSeeds() {
        if (optSeeds == null) {
            if (seeds == null) {
                throw new IllegalStateException();
            }
            optSeeds = new ArrayList<>(this.seeds.values());

            ListIterator<Seed> li = optSeeds.listIterator(optSeeds.size());
            BigInteger fix = BigInteger.ZERO;
            int counter = 0;
            Integer highest = null;
            while (li.hasPrevious()) {
                Seed previous = li.previous();
                if (highest == null) {
                    highest = previous.speed;
                }
                fix = fix.add(BigInteger.valueOf(previous.quantity() * (highest - previous.speed())));
                counter += previous.quantity();
                previous.fix(fix);
                previous.geCount(counter);
            }

            seeds = null;

        }
        return optSeeds;
    }

    private class Seed implements Comparable<Seed> {
        private long quantity;
        private final int speed;

        private BigInteger fix = BigInteger.ZERO;
        private int geCount;

        Seed(long quantity, int speed) {
            this.quantity = quantity;
            this.speed = speed;
        }

        public Seed(int speed) {
            this(1, speed);
        }

        @Override
        public String toString() {
            return "Seed [speed: " + speed + ", quantity: " + quantity + ", fix: " + fix + ", bigger: " + geCount + "]";
        }

        public long quantity() {
            return quantity;
        }

        public void increment() {
            quantity++;
        }

        @Override
        public int compareTo(Seed o) {
            return this.speed - o.speed;
        }

        public int speed() {
            return speed;
        }

        public void fix(BigInteger fix) {
            this.fix = fix;
        }

        public int geCount() {
            return geCount;
        }

        public void geCount(int counter) {
            geCount = counter;
        }
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int area = cin.nextInt();
        int cuts = cin.nextInt();

        sia sia = new sia(area);
        while (area-- > 0) {
            int speed = cin.nextInt();
            sia.addSeed(speed);
        }
        while (cuts-- > 0) {
            long day = cin.nextLong();
            long height = cin.nextLong();
            System.out.println(sia.result(day, height));
        }
    }

}