結果

問題 No.759 悪くない忘年会にしような！
ユーザー kimiyukikimiyuki
提出日時 2018-12-07 01:28:48
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 228 ms / 2,000 ms
コード長 3,007 bytes
コンパイル時間 2,672 ms
コンパイル使用メモリ 214,000 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-14 03:07:05
合計ジャッジ時間 7,525 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 2 ms
5,376 KB
testcase_32 AC 2 ms
5,376 KB
testcase_33 AC 11 ms
5,376 KB
testcase_34 AC 3 ms
5,376 KB
testcase_35 AC 7 ms
5,376 KB
testcase_36 AC 11 ms
5,376 KB
testcase_37 AC 4 ms
5,376 KB
testcase_38 AC 12 ms
5,376 KB
testcase_39 AC 4 ms
5,376 KB
testcase_40 AC 9 ms
5,376 KB
testcase_41 AC 10 ms
5,376 KB
testcase_42 AC 12 ms
5,376 KB
testcase_43 AC 13 ms
5,376 KB
testcase_44 AC 112 ms
5,376 KB
testcase_45 AC 113 ms
5,376 KB
testcase_46 AC 113 ms
5,376 KB
testcase_47 AC 113 ms
5,376 KB
testcase_48 AC 113 ms
5,376 KB
testcase_49 AC 14 ms
5,376 KB
testcase_50 AC 13 ms
5,376 KB
testcase_51 AC 13 ms
5,376 KB
testcase_52 AC 13 ms
5,376 KB
testcase_53 AC 112 ms
5,376 KB
testcase_54 AC 114 ms
5,376 KB
testcase_55 AC 113 ms
5,376 KB
testcase_56 AC 113 ms
5,376 KB
testcase_57 AC 113 ms
5,376 KB
testcase_58 AC 113 ms
5,376 KB
testcase_59 AC 113 ms
5,376 KB
testcase_60 AC 114 ms
5,376 KB
testcase_61 AC 113 ms
5,376 KB
testcase_62 AC 113 ms
5,376 KB
testcase_63 AC 228 ms
5,376 KB
testcase_64 AC 223 ms
5,376 KB
testcase_65 AC 98 ms
5,376 KB
testcase_66 AC 212 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = int(n) - 1; (i) >= 0; -- (i))
#define ALL(x) begin(x), end(x)
using namespace std;

template <class Monoid>
struct segment_tree {
    typedef typename Monoid::underlying_type underlying_type;
    int n;
    vector<underlying_type> a;
    const Monoid mon;
    segment_tree() = default;
    segment_tree(int a_n, underlying_type initial_value = Monoid().unit(), Monoid const & a_mon = Monoid()) : mon(a_mon) {
        n = 1; while (n < a_n) n *= 2;
        a.resize(2 * n - 1, mon.unit());
        fill(a.begin() + (n - 1), a.begin() + ((n - 1) + a_n), initial_value); // set initial values
        REP_R (i, n - 1) a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]); // propagate initial values
    }
    void point_set(int i, underlying_type z) { // 0-based
        assert (0 <= i and i <= n);
        a[i + n - 1] = z;
        for (i = (i + n) / 2; i > 0; i /= 2) { // 1-based
            a[i - 1] = mon.append(a[2 * i - 1], a[2 * i]);
        }
    }
    underlying_type range_concat(int l, int r) { // 0-based, [l, r)
        assert (0 <= l and l <= r and r <= n);
        underlying_type lacc = mon.unit(), racc = mon.unit();
        for (l += n, r += n; l < r; l /= 2, r /= 2) { // 1-based loop, 2x faster than recursion
            if (l % 2 == 1) lacc = mon.append(lacc, a[(l ++) - 1]);
            if (r % 2 == 1) racc = mon.append(a[(-- r) - 1], racc);
        }
        return mon.append(lacc, racc);
    }
};

struct max_monoid {
    typedef int underlying_type;
    int unit() const { return INT_MIN; }
    int append(int a, int b) const { return max(a, b); }
};

vector<bool> solve(int n, vector<int> const & a, vector<int> const & b, vector<int> const & c) {
    vector<int> order(n);
    iota(ALL(order), 0);
    sort(ALL(order), [&](int i, int j) { return a[i] > a[j]; });
    vector<bool> answer(n, true);
    int max_b = *max_element(ALL(b));
    segment_tree<max_monoid> segtree(max_b + 1);

    for (int l = 0; l < n; ) {
        int r = l + 1;
        while (r < n and a[order[r]] == a[order[l]]) ++ r;
        REP3 (m, l, r) {
            int i = order[m];
            if (segtree.range_concat(b[i], max_b + 1) >= c[i]) answer[i] = false;
        }
        REP3 (m, l, r) {
            int i = order[m];
            segtree.point_set(b[i], max(c[i], segtree.range_concat(b[i], b[i] + 1)));
        }
        REP3 (m, l, r) {
            int i = order[m];
            if (segtree.range_concat(b[i], b[i] + 1) > c[i]) answer[i] = false;
            if (segtree.range_concat(b[i] + 1, max_b + 1) >= c[i]) answer[i] = false;
        }
        l = r;
    }

    return answer;
}

int main() {
    int n; cin >> n;
    vector<int> a(n), b(n), c(n);
    REP (i, n) cin >> a[i] >> b[i] >> c[i];
    auto answer = solve(n, a, b, c);
    REP (i, n) if (answer[i]) {
        cout << i + 1 << endl;
    }
    return 0;
}
0