Submission #694924
Source Code Expand
using System; using System.Collections.Generic; using System.Linq; using System.IO; using System.Text; using Point = System.Tuple<double, double>; class Program { static void Main() { var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; var sc = new Scan(); long n; int m; sc.Multi(out n, out m); var p = new long[m]; var a = new Point[m]; for (int i = 0; i < m; ++i) { var b = sc.DoubleArr; p[i] = (long)b[0]; a[i] = new Point(b[1], b[2]); } var zip = p.Distinct().ToArray(); Array.Sort(zip); var ini = new Point(1, 0); var sg = new Segtree<Point>(zip.Length, ini, (x, y) => new Point(x.Item1 * y.Item1, x.Item2 * y.Item1 + y.Item2), ini); double max = 1, min = 1; for (int i = 0; i < m; ++i) { sg.update(Array.BinarySearch(zip, p[i]), a[i]); var q = sg.run(0, zip.Length - 1); var r = q.Item1 + q.Item2; max = Math.Max(max, r); min = Math.Min(min, r); } sw.WriteLine(min); sw.WriteLine(max); sw.Flush(); } } class Scan { public int Int { get { return int.Parse(Console.ReadLine().Trim()); } } public long Long { get { return long.Parse(Console.ReadLine().Trim()); } } public string Str { get { return Console.ReadLine().Trim(); } } public int[] IntArr { get { return Console.ReadLine().Trim().Split().Select(int.Parse).ToArray(); } } public int[] IntArrWithSep(char sep) { return Console.ReadLine().Trim().Split(sep).Select(int.Parse).ToArray(); } public long[] LongArr { get { return Console.ReadLine().Trim().Split().Select(long.Parse).ToArray(); } } public double[] DoubleArr { get { return Console.ReadLine().Split().Select(double.Parse).ToArray(); } } public string[] StrArr { get { return Console.ReadLine().Trim().Split(); } } public void Multi(out int a, out int b) { var arr = IntArr; a = arr[0]; b = arr[1]; } public void Multi(out int a, out int b, out int c) { var arr = IntArr; a = arr[0]; b = arr[1]; c = arr[2]; } public void Multi(out int a, out int b, out int c, out int d) { var arr = IntArr; a = arr[0]; b = arr[1]; c = arr[2]; d = arr[3]; } public void Multi(out int a, out string b) { var arr = StrArr; a = int.Parse(arr[0]); b = arr[1]; } public void Multi(out string a, out int b) { var arr = StrArr; a = arr[0]; b = int.Parse(arr[1]); } public void Multi(out int a, out int b, out string c) { var arr = StrArr; a = int.Parse(arr[0]); b = int.Parse(arr[1]); c = arr[2]; } public void Multi(out int a, out char b) { var arr = StrArr; a = int.Parse(arr[0]); b = arr[1][0]; } public void Multi(out char a, out int b) { var arr = StrArr; a = arr[0][0]; b = int.Parse(arr[1]); } public void Multi(out long a, out long b) { var arr = LongArr; a = arr[0]; b = arr[1]; } public void Multi(out long a, out int b) { var arr = LongArr; a = arr[0]; b = (int)arr[1]; } public void Multi(out int a, out long b) { var arr = LongArr; a = (int)arr[0]; b = arr[1]; } public void Multi(out string a, out string b) { var arr = StrArr; a = arr[0]; b = arr[1]; } } class Segtree<T> { int n; T[] tree; Func<T, T, T> f; T exnum; public Segtree(int m, Func<T, T, T> f, T ex) { this.f = f; this.exnum = ex; n = 1; while (n < m) n <<= 1; tree = new T[(n << 1) - 1]; for (int i = 0; i < tree.Length; i++) tree[i] = ex; } public Segtree(int m, T ini, Func<T, T, T> f, T ex) { this.f = f; this.exnum = ex; n = 1; while (n < m) n <<= 1; tree = new T[(n << 1) - 1]; for (int i = 0; i < tree.Length; i++) tree[i] = ini; for (int i = 0; i < m; ++i) update(i, ini); } public void update(int j, T x) { int i = j + n - 1; tree[i] = x; while (i > 0) { i = (i - 1) >> 1; tree[i] = f(tree[(i << 1) + 1], tree[(i << 1) + 2]); } } public T look(int i) { return tree[i + n - 1]; } // [s, t] public T run(int s, int t) { return query(s, t + 1, 0, 0, n); } T query(int s, int t, int k, int l, int r) { if (r <= s || t <= l) return exnum; if (s <= l && r <= t) return tree[k]; return f(query(s, t, (k << 1) + 1, l, (l + r) >> 1), query(s, t, (k + 1) << 1, (l + r) >> 1, r)); } }
Submission Info
Submission Time | |
---|---|
Task | D - タコヤキオイシクナール |
User | riantkb |
Language | C# (Mono 2.10.8.1) |
Score | 100 |
Code Size | 4661 Byte |
Status | AC |
Exec Time | 970 ms |
Memory | 18800 KB |
Judge Result
Set Name | small | large | ||||
---|---|---|---|---|---|---|
Score / Max Score | 50 / 50 | 50 / 50 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
small | small/small_00_sample_01.txt, small/small_00_sample_02.txt, small/small_00_sample_03.txt, small/small_00_sample_04.txt, small/small_01_min.txt, small/small_01_nom.txt, small/small_01_rand_00.txt, small/small_01_rand_01.txt, small/small_01_rand_02.txt, small/small_01_rand_03.txt, small/small_01_rand_04.txt, small/small_01_rand_05.txt, small/small_01_rand_06.txt, small/small_01_rand_07.txt, small/small_01_rand_08.txt, small/small_01_rand_09.txt, small/small_02_maxrand_00.txt, small/small_02_maxrand_01.txt, small/small_02_maxrand_02.txt, small/small_02_maxrand_03.txt, small/small_02_maxrand_04.txt, small/small_02_maxrand_05.txt, small/small_02_maxrand_06.txt, small/small_02_maxrand_07.txt, small/small_02_maxrand_08.txt, small/small_02_maxrand_09.txt, small/small_03_smalln_00.txt, small/small_03_smalln_01.txt, small/small_03_smalln_02.txt, small/small_03_smalln_03.txt, small/small_03_smalln_04.txt, small/small_03_smalln_05.txt, small/small_03_smalln_06.txt, small/small_03_smalln_07.txt, small/small_03_smalln_08.txt, small/small_03_smalln_09.txt, small/small_04_allplus_00.txt, small/small_04_allplus_01.txt, small/small_04_allplus_02.txt, small/small_05_allminus_00.txt, small/small_05_allminus_01.txt, small/small_05_allminus_02.txt |
large | small/small_00_sample_01.txt, small/small_00_sample_02.txt, small/small_00_sample_03.txt, small/small_00_sample_04.txt, small/small_01_min.txt, small/small_01_nom.txt, small/small_01_rand_00.txt, small/small_01_rand_01.txt, small/small_01_rand_02.txt, small/small_01_rand_03.txt, small/small_01_rand_04.txt, small/small_01_rand_05.txt, small/small_01_rand_06.txt, small/small_01_rand_07.txt, small/small_01_rand_08.txt, small/small_01_rand_09.txt, small/small_02_maxrand_00.txt, small/small_02_maxrand_01.txt, small/small_02_maxrand_02.txt, small/small_02_maxrand_03.txt, small/small_02_maxrand_04.txt, small/small_02_maxrand_05.txt, small/small_02_maxrand_06.txt, small/small_02_maxrand_07.txt, small/small_02_maxrand_08.txt, small/small_02_maxrand_09.txt, small/small_03_smalln_00.txt, small/small_03_smalln_01.txt, small/small_03_smalln_02.txt, small/small_03_smalln_03.txt, small/small_03_smalln_04.txt, small/small_03_smalln_05.txt, small/small_03_smalln_06.txt, small/small_03_smalln_07.txt, small/small_03_smalln_08.txt, small/small_03_smalln_09.txt, small/small_04_allplus_00.txt, small/small_04_allplus_01.txt, small/small_04_allplus_02.txt, small/small_05_allminus_00.txt, small/small_05_allminus_01.txt, small/small_05_allminus_02.txt, large/large_01_rand_00.txt, large/large_01_rand_01.txt, large/large_01_rand_02.txt, large/large_01_rand_03.txt, large/large_01_rand_04.txt, large/large_01_rand_05.txt, large/large_01_rand_06.txt, large/large_01_rand_07.txt, large/large_01_rand_08.txt, large/large_01_rand_09.txt, large/large_02_maxrand_00.txt, large/large_02_maxrand_01.txt, large/large_02_maxrand_02.txt, large/large_02_maxrand_03.txt, large/large_02_maxrand_04.txt, large/large_02_maxrand_05.txt, large/large_02_maxrand_06.txt, large/large_02_maxrand_07.txt, large/large_02_maxrand_08.txt, large/large_02_maxrand_09.txt, large/large_03_smalln_00.txt, large/large_03_smalln_01.txt, large/large_03_smalln_02.txt, large/large_03_smalln_03.txt, large/large_03_smalln_04.txt, large/large_03_smalln_05.txt, large/large_03_smalln_06.txt, large/large_03_smalln_07.txt, large/large_03_smalln_08.txt, large/large_03_smalln_09.txt, large/large_04_allplus_00.txt, large/large_04_allplus_01.txt, large/large_04_allplus_02.txt, large/large_05_allminus_00.txt, large/large_05_allminus_01.txt, large/large_05_allminus_02.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
large/large_01_rand_00.txt | AC | 528 ms | 13244 KB |
large/large_01_rand_01.txt | AC | 353 ms | 12384 KB |
large/large_01_rand_02.txt | AC | 917 ms | 18024 KB |
large/large_01_rand_03.txt | AC | 476 ms | 13912 KB |
large/large_01_rand_04.txt | AC | 655 ms | 16312 KB |
large/large_01_rand_05.txt | AC | 336 ms | 12252 KB |
large/large_01_rand_06.txt | AC | 507 ms | 14052 KB |
large/large_01_rand_07.txt | AC | 637 ms | 15924 KB |
large/large_01_rand_08.txt | AC | 846 ms | 17384 KB |
large/large_01_rand_09.txt | AC | 477 ms | 13912 KB |
large/large_02_maxrand_00.txt | AC | 944 ms | 18784 KB |
large/large_02_maxrand_01.txt | AC | 948 ms | 18784 KB |
large/large_02_maxrand_02.txt | AC | 961 ms | 18780 KB |
large/large_02_maxrand_03.txt | AC | 955 ms | 18760 KB |
large/large_02_maxrand_04.txt | AC | 970 ms | 18780 KB |
large/large_02_maxrand_05.txt | AC | 948 ms | 18780 KB |
large/large_02_maxrand_06.txt | AC | 946 ms | 18792 KB |
large/large_02_maxrand_07.txt | AC | 947 ms | 18784 KB |
large/large_02_maxrand_08.txt | AC | 950 ms | 18800 KB |
large/large_02_maxrand_09.txt | AC | 944 ms | 18756 KB |
large/large_03_smalln_00.txt | AC | 784 ms | 16952 KB |
large/large_03_smalln_01.txt | AC | 821 ms | 17968 KB |
large/large_03_smalln_02.txt | AC | 647 ms | 14052 KB |
large/large_03_smalln_03.txt | AC | 747 ms | 15660 KB |
large/large_03_smalln_04.txt | AC | 627 ms | 13928 KB |
large/large_03_smalln_05.txt | AC | 737 ms | 14896 KB |
large/large_03_smalln_06.txt | AC | 772 ms | 15724 KB |
large/large_03_smalln_07.txt | AC | 768 ms | 17328 KB |
large/large_03_smalln_08.txt | AC | 636 ms | 13920 KB |
large/large_03_smalln_09.txt | AC | 772 ms | 15780 KB |
large/large_04_allplus_00.txt | AC | 919 ms | 18780 KB |
large/large_04_allplus_01.txt | AC | 912 ms | 18736 KB |
large/large_04_allplus_02.txt | AC | 913 ms | 18772 KB |
large/large_05_allminus_00.txt | AC | 942 ms | 18724 KB |
large/large_05_allminus_01.txt | AC | 941 ms | 18788 KB |
large/large_05_allminus_02.txt | AC | 945 ms | 18780 KB |
small/small_00_sample_01.txt | AC | 150 ms | 10076 KB |
small/small_00_sample_02.txt | AC | 149 ms | 10076 KB |
small/small_00_sample_03.txt | AC | 151 ms | 10072 KB |
small/small_00_sample_04.txt | AC | 153 ms | 10076 KB |
small/small_01_min.txt | AC | 140 ms | 9924 KB |
small/small_01_nom.txt | AC | 141 ms | 9980 KB |
small/small_01_rand_00.txt | AC | 161 ms | 10464 KB |
small/small_01_rand_01.txt | AC | 154 ms | 10344 KB |
small/small_01_rand_02.txt | AC | 157 ms | 10332 KB |
small/small_01_rand_03.txt | AC | 162 ms | 10400 KB |
small/small_01_rand_04.txt | AC | 161 ms | 10328 KB |
small/small_01_rand_05.txt | AC | 159 ms | 10340 KB |
small/small_01_rand_06.txt | AC | 159 ms | 10332 KB |
small/small_01_rand_07.txt | AC | 161 ms | 10332 KB |
small/small_01_rand_08.txt | AC | 156 ms | 10200 KB |
small/small_01_rand_09.txt | AC | 161 ms | 10336 KB |
small/small_02_maxrand_00.txt | AC | 168 ms | 10464 KB |
small/small_02_maxrand_01.txt | AC | 168 ms | 10476 KB |
small/small_02_maxrand_02.txt | AC | 170 ms | 10464 KB |
small/small_02_maxrand_03.txt | AC | 164 ms | 10440 KB |
small/small_02_maxrand_04.txt | AC | 164 ms | 10460 KB |
small/small_02_maxrand_05.txt | AC | 174 ms | 10468 KB |
small/small_02_maxrand_06.txt | AC | 190 ms | 10448 KB |
small/small_02_maxrand_07.txt | AC | 179 ms | 10440 KB |
small/small_02_maxrand_08.txt | AC | 169 ms | 10372 KB |
small/small_02_maxrand_09.txt | AC | 168 ms | 10456 KB |
small/small_03_smalln_00.txt | AC | 164 ms | 10380 KB |
small/small_03_smalln_01.txt | AC | 164 ms | 10332 KB |
small/small_03_smalln_02.txt | AC | 166 ms | 10340 KB |
small/small_03_smalln_03.txt | AC | 162 ms | 10208 KB |
small/small_03_smalln_04.txt | AC | 168 ms | 10328 KB |
small/small_03_smalln_05.txt | AC | 169 ms | 10332 KB |
small/small_03_smalln_06.txt | AC | 168 ms | 10300 KB |
small/small_03_smalln_07.txt | AC | 165 ms | 10300 KB |
small/small_03_smalln_08.txt | AC | 169 ms | 10328 KB |
small/small_03_smalln_09.txt | AC | 164 ms | 10320 KB |
small/small_04_allplus_00.txt | AC | 170 ms | 10428 KB |
small/small_04_allplus_01.txt | AC | 165 ms | 10460 KB |
small/small_04_allplus_02.txt | AC | 165 ms | 10460 KB |
small/small_05_allminus_00.txt | AC | 168 ms | 10476 KB |
small/small_05_allminus_01.txt | AC | 170 ms | 10464 KB |
small/small_05_allminus_02.txt | AC | 169 ms | 10452 KB |