Submission #847808


Source Code Expand

Copy
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.PriorityQueue;
import java.io.BufferedWriter;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.AbstractCollection;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

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

    static class TaskE {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();
            int Q = in.nextInt();
            ArrayList<Long> q = new ArrayList<>();
            q.add((long) n);
            for (int i = 0; i < Q; ++i) {
                long x = in.nextLong();
                while (q.size() > 0 && q.get(q.size() - 1) >= x)
                    q.remove(q.size() - 1);
                q.add(x);
            }

            HashMap<Long, Long> d = new HashMap<>();
            PriorityQueue<Long> queue = new PriorityQueue<>();
            d.put(q.get(q.size() - 1), 1L);
            queue.add(-q.get(q.size() - 1));
            int cur = q.size() - 1;
            while (!queue.isEmpty()) {
                long val = -queue.poll();
                while (cur >= 0 && q.get(cur) >= val) --cur;
                if (cur == -1) continue;
                long prev = q.get(cur);
                long cnt = d.get(val);
                long r = val / prev;
                if (!d.containsKey(prev)) {
                    d.put(prev, cnt * r);
                    queue.add(-prev);
                } else {
                    d.put(prev, d.get(prev) + cnt * r);
                }
                if (val % prev != 0) {
                    long mod = val % prev;
                    if (!d.containsKey(mod)) {
                        d.put(mod, cnt);
                        queue.add(-mod);
                    } else {
                        d.put(mod, d.get(mod) + cnt);
                    }
                }
            }

            long[] res = new long[n + 1];
            for (int i = 1; i <= q.get(0); ++i) {
                if (!d.containsKey((long) i)) continue;
                long val = d.get((long) i);
                res[i] += val;
            }
            for (int i = n - 1; i > 0; --i)
                res[i] += res[i + 1];
            for (int i = 1; i <= n; ++i)
                out.printLine(res[i]);
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void printLine(Object... objects) {
            print(objects);
            writer.println();
        }

        public void close() {
            writer.close();
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buffer = new byte[10000];
        private int cur;
        private int count;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public static boolean isSpace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public int read() {
            if (count == -1) {
                throw new InputMismatchException();
            }
            try {
                if (cur >= count) {
                    cur = 0;
                    count = stream.read(buffer);
                    if (count <= 0)
                        return -1;
                }
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            return buffer[cur++];
        }

        public int readSkipSpace() {
            int c;
            do {
                c = read();
            } while (isSpace(c));
            return c;
        }

        public int nextInt() {
            int sgn = 1;
            int c = readSkipSpace();
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res = res * 10 + c - '0';
                c = read();
            } while (!isSpace(c));
            res *= sgn;
            return res;
        }

        public long nextLong() {
            long sgn = 1;
            int c = readSkipSpace();
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res = res * 10L + (long) (c - '0');
                c = read();
            } while (!isSpace(c));
            res *= sgn;
            return res;
        }

    }
}

Submission Info

Submission Time
Task E - Sequential operations on Sequence
User ilyakor
Language Java8 (OpenJDK 1.8.0)
Score 1400
Code Size 6034 Byte
Status AC
Exec Time 1813 ms
Memory 70380 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 1091 ms 23428 KB
02.txt AC 1813 ms 21968 KB
03.txt AC 358 ms 21900 KB
04.txt AC 390 ms 21928 KB
05.txt AC 362 ms 21924 KB
06.txt AC 1106 ms 60836 KB
07.txt AC 1266 ms 64936 KB
08.txt AC 1226 ms 64276 KB
09.txt AC 1202 ms 61968 KB
10.txt AC 1146 ms 61336 KB
11.txt AC 1054 ms 57944 KB
12.txt AC 1298 ms 62696 KB
13.txt AC 1306 ms 62836 KB
14.txt AC 1174 ms 59520 KB
15.txt AC 1131 ms 58524 KB
16.txt AC 1278 ms 61508 KB
17.txt AC 1226 ms 64256 KB
18.txt AC 1154 ms 61364 KB
19.txt AC 1077 ms 57004 KB
20.txt AC 1270 ms 65656 KB
21.txt AC 1262 ms 70380 KB
22.txt AC 1290 ms 65108 KB
23.txt AC 946 ms 52520 KB
24.txt AC 1018 ms 52280 KB
25.txt AC 826 ms 44424 KB
26.txt AC 774 ms 45124 KB
27.txt AC 282 ms 18516 KB
28.txt AC 290 ms 20228 KB
29.txt AC 270 ms 19024 KB
30.txt AC 310 ms 20332 KB
31.txt AC 170 ms 8148 KB
32.txt AC 294 ms 19576 KB
33.txt AC 154 ms 8276 KB
34.txt AC 306 ms 21412 KB
35.txt AC 158 ms 8148 KB
36.txt AC 162 ms 8148 KB
s1.txt AC 158 ms 8148 KB
s2.txt AC 167 ms 8148 KB