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
AC × 42
AC × 78
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