Submission #847234


Source Code Expand

Copy
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int nq = in.nextInt();
            long[] q = new long[nq + 1];
            q[0] = n;
            for (int i = 0; i < nq; ++i) {
                q[i + 1] = in.nextLong();
            }
            int ptr = 0;
            for (int i = 0; i <= nq; ++i) {
                q[ptr++] = q[i];
                while (ptr >= 2 && q[ptr - 1] <= q[ptr - 2]) {
                    q[ptr - 2] = q[ptr - 1];
                    --ptr;
                }
            }
            q = Arrays.copyOf(q, ptr);
            long[] toPropagate = new long[ptr];
            toPropagate[ptr - 1] = 1;
            long[] res = new long[n + 1];
            for (int i = ptr - 1; i >= 0; --i) {
                long val = q[i];
                int upto = i;
                long prop = toPropagate[i];
                while (true) {
                    int at = Arrays.binarySearch(q, 0, upto, val);
                    if (at < 0) {
                        at = -at - 2;
                    }
                    if (at < 0) break;
                    long whole = val / q[at];
                    toPropagate[at] += prop * whole;
                    upto = at;
                    val %= q[at];
                }
                res[0] += prop;
                res[((int) val)] -= prop;
            }
            for (int i = 1; i < n; ++i) {
                res[i] += res[i - 1];
            }
            for (int i = 0; i < n; ++i) {
                out.println(res[i]);
            }
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}

Submission Info

Submission Time
Task E - Sequential operations on Sequence
User Petr
Language Java8 (OpenJDK 1.8.0)
Score 1400
Code Size 3308 Byte
Status AC
Exec Time 817 ms
Memory 25412 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1400 / 1400
Status
AC × 2
AC × 38
Set Name Test Cases
Sample s1.txt, s2.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, s1.txt, s2.txt
Case Name Status Exec Time Memory
01.txt AC 817 ms 23316 KB
02.txt AC 436 ms 22928 KB
03.txt AC 455 ms 22884 KB
04.txt AC 419 ms 22800 KB
05.txt AC 451 ms 22472 KB
06.txt AC 523 ms 23744 KB
07.txt AC 463 ms 24044 KB
08.txt AC 483 ms 24052 KB
09.txt AC 475 ms 23364 KB
10.txt AC 527 ms 23188 KB
11.txt AC 463 ms 23036 KB
12.txt AC 463 ms 23900 KB
13.txt AC 467 ms 25412 KB
14.txt AC 479 ms 23328 KB
15.txt AC 475 ms 23916 KB
16.txt AC 479 ms 23372 KB
17.txt AC 479 ms 22616 KB
18.txt AC 459 ms 23312 KB
19.txt AC 467 ms 22696 KB
20.txt AC 499 ms 23484 KB
21.txt AC 487 ms 22528 KB
22.txt AC 415 ms 23016 KB
23.txt AC 483 ms 22968 KB
24.txt AC 423 ms 22580 KB
25.txt AC 435 ms 23820 KB
26.txt AC 423 ms 23748 KB
27.txt AC 356 ms 21704 KB
28.txt AC 344 ms 21752 KB
29.txt AC 363 ms 21688 KB
30.txt AC 343 ms 21836 KB
31.txt AC 159 ms 8148 KB
32.txt AC 251 ms 15628 KB
33.txt AC 159 ms 8144 KB
34.txt AC 297 ms 20240 KB
35.txt AC 163 ms 8276 KB
36.txt AC 167 ms 8148 KB
s1.txt AC 163 ms 8272 KB
s2.txt AC 167 ms 8148 KB