#699022 (C++14) No.1675 Strange Minimum Query

提出ソース

結果

問題	No.1675 Strange Minimum Query
ユーザー	rokahikou1
提出日時	2021-09-11 20:27:31
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	11,920 bytes
コンパイル時間	2,055 ms
コンパイル使用メモリ	187,460 KB
実行使用メモリ	10,640 KB
最終ジャッジ日時	2024-06-23 05:08:59
合計ジャッジ時間	7,168 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	TLE	-
testcase_03	AC	126 ms 7,168 KB
testcase_04	AC	115 ms 7,240 KB
testcase_05	AC	16 ms 6,944 KB
testcase_06	AC	151 ms 7,808 KB
testcase_07	AC	163 ms 8,076 KB
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	AC	115 ms 10,640 KB
testcase_14	AC	144 ms 10,636 KB
testcase_15	AC	135 ms 10,508 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	31 ms 6,940 KB
testcase_18	AC	44 ms 6,944 KB
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	AC	161 ms 9,852 KB
testcase_23	AC	128 ms 6,948 KB
testcase_24	AC	113 ms 7,012 KB
testcase_25	AC	84 ms 6,948 KB
testcase_26	WA	-
testcase_27	AC	106 ms 9,180 KB
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	AC	164 ms 7,824 KB
testcase_32	AC	210 ms 10,412 KB
testcase_33	AC	215 ms 10,516 KB
testcase_34	AC	206 ms 10,512 KB
testcase_35	AC	180 ms 10,512 KB
testcase_36	AC	179 ms 10,640 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma region Macros
#include <bits/stdc++.h>
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for(int(i) = (n)-1; (i) >= 0; (i)--)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define ROF(i, m, n) for(int(i) = (n)-1; (i) >= (m); (i)--)
#define ALL(v) (v).begin(), (v).end()
#define LLA(v) (v).rbegin(), (v).rend()
#define SZ(v) (int)(v).size()
#define INT(...)     \
    int __VA_ARGS__; \
    read(__VA_ARGS__)
#define LL(...)     \
    ll __VA_ARGS__; \
    read(__VA_ARGS__)
#define DOUBLE(...)     \
    double __VA_ARGS__; \
    read(__VA_ARGS__)
#define CHAR(...)     \
    char __VA_ARGS__; \
    read(__VA_ARGS__)
#define STRING(...)     \
    string __VA_ARGS__; \
    read(__VA_ARGS__)
#define VEC(type, name, size) \
    vector<type> name(size);  \
    read(name)
#define VEC2(type, name, height, width)                     \
    vector<vector<type>> name(height, vector<type>(width)); \
    read(name)
#define DVEC(type, name1, name2, size)     \
    vector<type> name1(size), name2(size); \
    read(name1, name2)
#define TVEC(type, name1, name2, name3, size)           \
    vector<type> name1(size), name2(size), name3(size); \
    read(name1, name2, name3)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;
const char newl = '\n';
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
template <class T> inline bool between(T x, T l, T r) {
    return l <= x && x < r;
}
template <class T> inline vector<T> make_vec(size_t a, T val) {
    return vector<T>(a, val);
}
template <class... Ts> inline auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec(ts...))>(a, make_vec(ts...));
}
void read() {}
template <class T> inline void read(T &a) { cin >> a; }
template <class T, class S> inline void read(pair<T, S> &p) {
    read(p.first), read(p.second);
}
template <class T> inline void read(vector<T> &v) {
    for(auto &&a : v)
        read(a);
}
template <class T, class U> inline void read(vector<T> &a, vector<U> &b) {
    for(int i = 0; i < a.size(); i++) {
        read(a[i]);
        read(b[i]);
    }
}
template <class T, class U, class V>
inline void read(vector<T> &a, vector<U> &b, vector<V> &c) {
    for(int i = 0; i < a.size(); i++) {
        read(a[i]);
        read(b[i]);
        read(c[i]);
    }
}
template <class Head, class... Tail>
inline void read(Head &head, Tail &...tail) {
    read(head), read(tail...);
}
template <class T> void _write(const T &a) { cout << a; }
template <class T, class U> void _write(const std::pair<T, U> &a) { cout << a.first << ' ' << a.second; }
template <class T> void write(const T &a) {
    _write(a);
    cout << newl;
}
template <class T> void write(const vector<T> &a) {
    for(int i = 0; i < a.size(); i++) {
        _write(a[i]);
        cout << (i + 1 == a.size() ? newl : ' ');
    }
}
template <class Head, class... Tail>
void write(const Head &head, const Tail &...tail) {
    _write(head);
    cout << ' ';
    write(tail...);
}
template <class T> void writel(const T &a) { cout << a << '\n'; }
template <class T> void writel(const vector<T> &a) {
    for(int i = 0; i < a.size(); i++) {
        _write(a[i]);
        cout << newl;
    }
}
template <class Head, class... Tail>
void writel(const Head &head, const Tail &...tail) {
    _write(head);
    cout << newl;
    write(tail...);
}
template <class T> void _debug(const T &a) { cerr << a; }
template <class T, class U> void _debug(const std::pair<T, U> &a) { cerr << a.first << ' ' << a.second; }
template <class T> void debug(const T &a) {
    _debug(a);
    cerr << newl;
}
template <class T> void debug(const vector<T> &a) {
    for(int i = 0; i < a.size(); i++) {
        _debug(a[i]);
        cerr << (i + 1 == a.size() ? newl : ' ');
    }
}
template <class Head, class... Tail>
void debug(const Head &head, const Tail &...tail) {
    _debug(head);
    cerr << ' ';
    debug(tail...);
}
template <class T> void debugl(const T &a) { cerr << a << '\n'; }
template <class T> void debugl(const vector<T> &a) {
    for(int i = 0; i < a.size(); i++) {
        _debug(a[i]);
        cerr << newl;
    }
}
template <class Head, class... Tail>
void debugl(const Head &head, const Tail &...tail) {
    _debug(head);
    cerr << newl;
    debug(tail...);
}
template <class T> auto sum(const vector<T> &a) {
    return accumulate(ALL(a), T(0));
}
template <class T> auto min(const vector<T> &a) { return *min_element(ALL(a)); }
template <class T> auto max(const vector<T> &a) { return *max_element(ALL(a)); }
template <class T, class U> void msort(vector<T> &a, vector<U> &b) {
    assert(a.size() == b.size());
    vector<pair<T, U>> ab(a.size());
    for(int i = 0; i < a.size(); i++)
        ab[i] = {a[i], b[i]};
    sort(ALL(ab));
    for(int i = 0; i < a.size(); i++) {
        a[i] = ab[i].first;
        b[i] = ab[i].second;
    }
}
template <class T, class U, class V>
void msort(vector<T> &a, vector<U> &b, vector<V> &c) {
    assert(a.size() == b.size() && b.size() == c.size());
    vector<tuple<T, U, V>> abc(a.size());
    for(int i = 0; i < a.size(); i++)
        abc[i] = {a[i], b[i], c[i]};
    sort(ALL(abc));
    for(int i = 0; i < a.size(); i++) {
        a[i] = get<0>(abc[i]);
        b[i] = get<1>(abc[i]);
        c[i] = get<2>(abc[i]);
    }
}
template <class T, class U> inline bool chmax(T &a, U b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T, class U> inline bool chmin(T &a, U b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}
int digit(ll a) {
    ll ret = 0;
    while(a && ++ret)
        a /= 10;
    return ret;
}
int digit_sum(ll a) {
    ll ret = 0;
    while(a) {
        ret += a % 10;
        a /= 10;
    }
    return ret;
}
ll llpow(ll a, ll n) {
    ll ret = 1;
    rep(i, n) ret *= a;
    return ret;
}
inline int bsf(int v) { return __builtin_ctz(v); } // 最下位の1が下から何番目か
inline int bsf(ll v) { return __builtin_ctzll(v); }
inline int bsr(int v) {
    return 31 - __builtin_clz(v);
} // 最上位の1が下から何番目か
inline int bsr(ll v) { return 63 - __builtin_clzll(v); }
inline int lsb(int v) { return v & -v; } // 最下位の1だけ残す
inline ll lsb(ll v) { return v & -v; }
inline int msb(int v) { return 1 << bsr(v); } // 最上位の1だけ残す
inline ll msb(ll v) { return 1LL << bsr(v); }
struct IO {
    IO() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout << fixed << setprecision(10);
    }
} io;
#pragma endregion

/*** DualSegmentTree ***/
template <class F> class DualSegTree {
  private:
    using Composition = function<F(F, F)>;

    size_t n;
    const Composition composition;
    const F oe;
    vector<F> lazy;

    // 子に伝播
    inline void propagate(int k) {
        if(lazy[k] != oe) {
            lazy[2 * k] = composition(lazy[2 * k], lazy[k]);
            lazy[2 * k + 1] = composition(lazy[2 * k + 1], lazy[k]);
            lazy[k] = oe;
        }
    }

    // 上から伝播
    inline void thrust(int k) {
        for(int i = 31 - __builtin_clz(k); i > 0; i--) {
            if((k >> i) >= 1)
                propagate(k >> i);
        }
    }

  public:
    DualSegTree(int sz, const Composition _h, const F &_oe)
        : composition(_h), oe(_oe) {
        n = 1;
        while(n < sz) {
            n <<= 1;
        }
        lazy.resize(2 * n, oe);
    }

    DualSegTree(const vector<F> &v, const Composition _h, const F &_oe)
        : composition(_h), oe(_oe) {
        int sz = v.size();
        n = 1;
        while(n < sz) {
            n <<= 1;
        }
        lazy.resize(2 * n, oe);
        for(int i = 0; i < sz; i++)
            set(i, v[i]);
    }

    void set(int k, const F &x) {
        k += n;
        thrust(k);
        lazy[k] = x;
    }

    // [L,R)区間作用
    void update(int L, int R, const F &x) {
        L += n, R += n;
        int L0 = L / (L & -L), R0 = R / (R & -R) - 1;
        thrust(L0);
        thrust(R0);
        while(L < R) {
            if(L & 1) {
                lazy[L] = composition(lazy[L], x);
                L++;
            }
            if(R & 1) {
                R--;
                lazy[R] = composition(lazy[R], x);
            }
            L >>= 1;
            R >>= 1;
        }
    }

    // 一点取得
    F at(int k) {
        k += n;
        thrust(k);
        return lazy[k];
    }

    F operator[](int k) { return at(k); }
};

using F = int;
F id() { return 0; }
F composition(F f, F g) { return g; };

template <class S> struct SegmentTree {
  private:
    using Op = function<S(S, S)>;
    const Op op;
    const S e;
    int n;
    int org_size;
    vector<S> dat;

  public:
    void set(int k, S a) { dat[k + n] = a; }

    void build() {
        for(int i = n - 1; i > 0; i--) {
            dat[i] = op(dat[2 * i], dat[2 * i + 1]);
        }
    }

    void update(int k, const S &a) {
        k += n;
        dat[k] = a;
        while(k >>= 1) {
            dat[k] = op(dat[k * 2], dat[k * 2 + 1]);
        }
    }

    S at(int a) const { return query(a, a + 1); }

    // query for [a,b)
    S query(int a, int b) const {
        S vl = e, vr = e;
        a += n, b += n;
        for(; a < b; a >>= 1, b >>= 1) {
            if(a & 1)
                vl = op(vl, dat[a++]);
            if(b & 1)
                vr = op(dat[--b], vr);
        }
        return op(vl, vr);
    }

    int max_right(int l, function<bool(S)> f) const {
        if(l == org_size)
            return org_size;
        l += n;
        S cum = e;
        do {
            while(l % 2 == 0)
                l >>= 1;
            if(!f(op(cum, dat[l]))) {
                while(l < n) {
                    l = 2 * l;
                    if(f(op(cum, dat[l]))) {
                        cum = op(cum, dat[l]);
                        l++;
                    }
                }
                return l - n;
            }
            cum = op(cum, dat[l]);
            l++;
        } while((l & -l) != l);
        return org_size;
    }

    // !!未verify!!
    int min_left(int r, function<bool(S)> f) const {
        if(r == 0)
            return 0;
        r += n;
        S cum = e;
        do {
            r--;
            while(r > 1 && (r % 2))
                r >>= 1;
            if(!f(op(dat[r], cum))) {
                while(r < n) {
                    r = 2 * r + 1;
                    if(f(op(dat[r], cum))) {
                        cum = op(dat[r], cum);
                        r--;
                    }
                }
                return r + 1 - n;
            }
            cum = op(dat[r], cum);
        } while((r & (-r) != r));
        return 0;
    }

    SegmentTree(int _n, const Op op, const S &e) : op(op), e(e) {
        org_size = _n;
        n = 1;
        while(n < org_size)
            n *= 2;
        dat.assign(2 * n, e);
    }

    SegmentTree(const vector<S> &v, const Op op, const S &e) : op(op), e(e) {
        org_size = v.size();
        n = 1;
        while(n < org_size)
            n *= 2;
        dat.assign(2 * n, e);
        for(int i = 0; i < org_size; i++)
            set(i, v[i]);
        build();
    }
};

using S = int;
S op(const S &a, const S &b) { return min(a, b); };

void solve() {
    INT(n, Q);
    TVEC(int, l, r, b, Q);
    msort(b, l, r);
    DualSegTree<F> dual(n, composition, id());
    SegmentTree<S> seg(n, op, INF);
    rep(i, Q) {
        l[i]--;
        dual.update(l[i], r[i], b[i]);
    }
    vector<int> res(n);
    rep(i, n) res[i] = dual[i];
    rep(i, n) {
        seg.set(i, res[i]);
    }
    seg.build();
    rep(i, Q) {
        if(seg.query(l[i], r[i]) != b[i]) {
            write(-1);
            return;
        }
    }
    write(res);
}

int main() {
    int t = 1;
    // cin >> t;
    while(t--) {
        solve();
    }
}

yukicoder

結果

テストケース

ソースコード