Submission #1083406
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;FastScanner in = new FastScanner(inputStream);PrintWriter out = new PrintWriter(outputStream);
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; FastScanner in = new FastScanner(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, FastScanner in, PrintWriter out) { int n = in.nextInt(); int m = in.nextInt(); Segment[] s = new Segment[n]; for (int i = 0; i < n; i++) { int l = in.nextInt(); int r = in.nextInt(); s[i] = new Segment(l, r); } Arrays.sort(s); int p = 0; Tree tree = new Tree(m + 1); for (int d = 1; d <= m; d++) { int ans = 0; while (p < n && s[p].len < d) { tree.add(s[p].l, s[p].r, 1); ++p; } ans += n - p; // long segments will always hit for (int i = 0; i <= m; i += d) { ans += tree.get(i); } out.println(ans); } } class Segment implements Comparable<Segment> { int l; int r; int len; Segment(int l, int r) { this.l = l; this.r = r; this.len = r - l + 1; } public int compareTo(Segment o) { return len - o.len; } } class Tree { int n; int[] add; Tree(int n) { this.n = n; add = new int[4 * n]; } void add(int l, int r, int val) { add(0, l, r, 0, n - 1, val); } int get(int x) { return get(0, x, 0, n - 1); } private int get(int root, int x, int L, int R) { if (L == R) { return add[root]; } push(root); int M = (L + R) / 2; if (x <= M) { return get(2 * root + 1, x, L, M); } return get(2 * root + 2, x, M + 1, R); } private void add(int root, int l, int r, int L, int R, int val) { if (l > r || l > R || L > r || L > R) { return; } if (l == L && r == R) { add[root] += val; return; } push(root); int M = (L + R) / 2; add(2 * root + 1, l, Math.min(M, r), L, M, val); add(2 * root + 2, Math.max(M + 1, l), r, M + 1, R, val); } void push(int root) { add[2 * root + 1] += add[root]; add[2 * root + 2] += add[root]; add[root] = 0; } } } static class FastScanner { private BufferedReader in; private StringTokenizer st; public FastScanner(InputStream stream) { in = new BufferedReader(new InputStreamReader(stream)); } public String next() { while (st == null || !st.hasMoreTokens()) { try { String rl = in.readLine(); if (rl == null) { return null; } st = new StringTokenizer(rl); } catch (IOException e) { throw new RuntimeException(e); } } return st.nextToken(); } public int nextInt() { return Integer.parseInt(next()); } } }
Submission Info
Submission Time | |
---|---|
Task | E - Snuke Line |
User | fetetriste |
Language | Java8 (OpenJDK 1.8.0) |
Score | 700 |
Code Size | 3293 Byte |
Status | AC |
Exec Time | 1188 ms |
Memory | 55636 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 700 / 700 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt |
All | 00_example_01.txt, 00_example_02.txt, 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, 37.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | AC | 111 ms | 8532 KB |
00_example_02.txt | AC | 99 ms | 8404 KB |
01.txt | AC | 108 ms | 8400 KB |
02.txt | AC | 136 ms | 9552 KB |
03.txt | AC | 119 ms | 8788 KB |
04.txt | AC | 101 ms | 8528 KB |
05.txt | AC | 116 ms | 8788 KB |
06.txt | AC | 119 ms | 9040 KB |
07.txt | AC | 99 ms | 8404 KB |
08.txt | AC | 125 ms | 9044 KB |
09.txt | AC | 111 ms | 9044 KB |
10.txt | AC | 114 ms | 9040 KB |
11.txt | AC | 876 ms | 55000 KB |
12.txt | AC | 1149 ms | 55092 KB |
13.txt | AC | 730 ms | 55636 KB |
14.txt | AC | 864 ms | 55184 KB |
15.txt | AC | 778 ms | 54684 KB |
16.txt | AC | 1065 ms | 55016 KB |
17.txt | AC | 995 ms | 55256 KB |
18.txt | AC | 617 ms | 55332 KB |
19.txt | AC | 1104 ms | 55388 KB |
20.txt | AC | 1005 ms | 55172 KB |
21.txt | AC | 1188 ms | 55264 KB |
22.txt | AC | 1170 ms | 55116 KB |
23.txt | AC | 1171 ms | 54960 KB |
24.txt | AC | 864 ms | 54592 KB |
25.txt | AC | 677 ms | 54704 KB |
26.txt | AC | 617 ms | 55088 KB |
27.txt | AC | 964 ms | 55040 KB |
28.txt | AC | 811 ms | 54620 KB |
29.txt | AC | 941 ms | 54600 KB |
30.txt | AC | 797 ms | 54716 KB |
31.txt | AC | 972 ms | 55344 KB |
32.txt | AC | 799 ms | 54680 KB |
33.txt | AC | 780 ms | 54624 KB |
34.txt | AC | 886 ms | 54708 KB |
35.txt | AC | 938 ms | 55024 KB |
36.txt | AC | 98 ms | 8400 KB |
37.txt | AC | 315 ms | 14700 KB |