Submission #4784678


Source Code Expand

Copy
#include <algorithm>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)

template <class T>
class SegTree {
    int n;                       // 葉の数
    vector<T> data;              // データを格納するvector
    T def;                       // 初期値かつ単位元
    function<T(T, T)> operation; // 区間クエリで使う処理
    function<T(T, T)> update;    // 点更新で使う処理

    // 区間[a,b)の総和。ノードk=[l,r)に着目している。
    T _query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return def; // 交差しない
        if (a <= l && r <= b)
            return data[k]; // a,l,r,bの順で完全に含まれる
        else {
            T c1 = _query(a, b, 2 * k + 1, l, (l + r) / 2); // 左の子
            T c2 = _query(a, b, 2 * k + 2, (l + r) / 2, r); // 右の子
            return operation(c1, c2);
        }
    }

  public:
    // _n:必要サイズ, _def:初期値かつ単位元, _operation:クエリ関数,
    // _update:更新関数
    SegTree(size_t _n, T _def, function<T(T, T)> _operation,
            function<T(T, T)> _update)
        : def(_def), operation(_operation), update(_update) {
        n = 1;
        while (n < _n) {
            n *= 2;
        }
        data = vector<T>(2 * n - 1, def);
    }

    // 場所i(0-indexed)の値をxで更新
    void change(int i, T x) {
        i += n - 1;
        data[i] = update(data[i], x);
        while (i > 0) {
            i = (i - 1) / 2;
            data[i] = operation(data[i * 2 + 1], data[i * 2 + 2]);
        }
    }

    // [a, b)の区間クエリを実行
    T query(int a, int b) {
        return _query(a, b, 0, 0, n);
    }

    // 添字でアクセス
    T operator[](int i) {
        return data[i + n - 1];
    }
};

// 座標圧縮
template <typename T>
int compress(vector<T> x, map<T, int> &zip, vector<int> &unzip) {
    sort(x.begin(), x.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    for (int i = 0; i < x.size(); i++) {
        zip[x[i]] = i;
        unzip[i] = x[i];
    }
    return x.size();
}

struct box {
    double a, b;
};

int main(void) {
    long long N;
    int M;
    cin >> N >> M;

    vector<long long> p(M);
    vector<double> a(M), b(M);
    rep(i, M) {
        cin >> p[i] >> a[i] >> b[i];
        p[i]--;
    }

    map<long long, int> zip;
    vector<int> unzip(M);
    N = compress(p, zip, unzip);

    SegTree<box> st(N, box{1, 0},
                    [](box s, box t) {
                        return box{s.a * t.a, s.b * t.a + t.b};
                    },
                    [](box s, box t) { return t; });
    double ma = 1, mi = 1;
    rep(i, M) {
        st.change(zip[p[i]], box{a[i], b[i]});
        box whole = st.query(0, N);
        double v = whole.a + whole.b;
        ma = max(ma, v);
        mi = min(mi, v);
    }

    cout << fixed << setprecision(15) << mi << endl << ma << endl;

    return 0;
}

Submission Info

Submission Time
Task D - タコヤキオイシクナール
User furuya1223
Language C++14 (GCC 5.4.1)
Score 100
Code Size 3214 Byte
Status
Exec Time 138 ms
Memory 6776 KB

Test Cases

Set Name Score / Max Score Test Cases
small 50 / 50 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 50 / 50 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 41 ms 2304 KB
large/large_01_rand_01.txt 32 ms 1920 KB
large/large_01_rand_02.txt 127 ms 6544 KB
large/large_01_rand_03.txt 52 ms 3040 KB
large/large_01_rand_04.txt 85 ms 4104 KB
large/large_01_rand_05.txt 29 ms 1792 KB
large/large_01_rand_06.txt 55 ms 3160 KB
large/large_01_rand_07.txt 80 ms 3984 KB
large/large_01_rand_08.txt 112 ms 6076 KB
large/large_01_rand_09.txt 53 ms 3164 KB
large/large_02_maxrand_00.txt 135 ms 6776 KB
large/large_02_maxrand_01.txt 136 ms 6776 KB
large/large_02_maxrand_02.txt 138 ms 6776 KB
large/large_02_maxrand_03.txt 136 ms 6776 KB
large/large_02_maxrand_04.txt 135 ms 6776 KB
large/large_02_maxrand_05.txt 135 ms 6776 KB
large/large_02_maxrand_06.txt 135 ms 6776 KB
large/large_02_maxrand_07.txt 135 ms 6776 KB
large/large_02_maxrand_08.txt 135 ms 6776 KB
large/large_02_maxrand_09.txt 137 ms 6776 KB
large/large_03_smalln_00.txt 112 ms 3960 KB
large/large_03_smalln_01.txt 116 ms 4600 KB
large/large_03_smalln_02.txt 89 ms 2048 KB
large/large_03_smalln_03.txt 106 ms 2936 KB
large/large_03_smalln_04.txt 84 ms 2048 KB
large/large_03_smalln_05.txt 102 ms 2680 KB
large/large_03_smalln_06.txt 108 ms 3704 KB
large/large_03_smalln_07.txt 110 ms 3960 KB
large/large_03_smalln_08.txt 88 ms 2048 KB
large/large_03_smalln_09.txt 109 ms 3704 KB
large/large_04_allplus_00.txt 133 ms 6776 KB
large/large_04_allplus_01.txt 132 ms 6776 KB
large/large_04_allplus_02.txt 132 ms 6776 KB
large/large_05_allminus_00.txt 135 ms 6776 KB
large/large_05_allminus_01.txt 135 ms 6776 KB
large/large_05_allminus_02.txt 135 ms 6776 KB
small/small_00_sample_01.txt 1 ms 256 KB
small/small_00_sample_02.txt 1 ms 256 KB
small/small_00_sample_03.txt 1 ms 256 KB
small/small_00_sample_04.txt 1 ms 256 KB
small/small_01_min.txt 1 ms 256 KB
small/small_01_nom.txt 1 ms 256 KB
small/small_01_rand_00.txt 3 ms 384 KB
small/small_01_rand_01.txt 2 ms 256 KB
small/small_01_rand_02.txt 2 ms 256 KB
small/small_01_rand_03.txt 2 ms 256 KB
small/small_01_rand_04.txt 2 ms 256 KB
small/small_01_rand_05.txt 2 ms 256 KB
small/small_01_rand_06.txt 2 ms 256 KB
small/small_01_rand_07.txt 2 ms 256 KB
small/small_01_rand_08.txt 1 ms 256 KB
small/small_01_rand_09.txt 2 ms 256 KB
small/small_02_maxrand_00.txt 3 ms 384 KB
small/small_02_maxrand_01.txt 3 ms 384 KB
small/small_02_maxrand_02.txt 3 ms 384 KB
small/small_02_maxrand_03.txt 3 ms 384 KB
small/small_02_maxrand_04.txt 3 ms 384 KB
small/small_02_maxrand_05.txt 3 ms 384 KB
small/small_02_maxrand_06.txt 3 ms 384 KB
small/small_02_maxrand_07.txt 3 ms 384 KB
small/small_02_maxrand_08.txt 3 ms 384 KB
small/small_02_maxrand_09.txt 3 ms 384 KB
small/small_03_smalln_00.txt 3 ms 384 KB
small/small_03_smalln_01.txt 3 ms 256 KB
small/small_03_smalln_02.txt 3 ms 256 KB
small/small_03_smalln_03.txt 3 ms 256 KB
small/small_03_smalln_04.txt 3 ms 384 KB
small/small_03_smalln_05.txt 3 ms 384 KB
small/small_03_smalln_06.txt 3 ms 256 KB
small/small_03_smalln_07.txt 3 ms 256 KB
small/small_03_smalln_08.txt 3 ms 256 KB
small/small_03_smalln_09.txt 3 ms 256 KB
small/small_04_allplus_00.txt 3 ms 384 KB
small/small_04_allplus_01.txt 3 ms 384 KB
small/small_04_allplus_02.txt 3 ms 384 KB
small/small_05_allminus_00.txt 3 ms 384 KB
small/small_05_allminus_01.txt 3 ms 384 KB
small/small_05_allminus_02.txt 3 ms 384 KB