結果

問題 No.1675 Strange Minimum Query
コンテスト
ユーザー vjudge1
提出日時 2025-12-08 18:53:46
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 3,747 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,001 ms
コンパイル使用メモリ 217,848 KB
実行使用メモリ 17,408 KB
最終ジャッジ日時 2025-12-08 18:53:58
合計ジャッジ時間 11,621 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other AC * 3 WA * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fi first
#define se second
#define all(x) x.begin(), x.end()

const int N = 1e5 + 5;
const ll MOD = 1e9 + 7;
// const ll MOD2 = 998244353;
const ll inf = (1LL << 62);

int n, q, a[N];
int l[N], r[N], p[N];

namespace sub1 {
    bool check() {
        return n <= 10;
    }

    void solve() {
        for (int i = 1; i <= n; i++)
            a[i] = i;

        do {
            bool ok = true;
            for (int i = 1; i <= q; i++) {
                int gmin = *min_element(a + l[i], a + r[i] + 1);
                if (gmin != p[i]) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                for (int i = 1; i <= n; i++)
                    cout << a[i] << ' ';
                return;
            }
        } while (next_permutation(a + 1, a + n + 1));

        for (int i = 1; i <= n; i++)
            cout << -1 << ' ';
    }
}

namespace sub2 {
    bool check() {
        for (int i = 1; i < q; i++)
            if (r[i] >= l[i + 1])
                return false;
        return true;
    }

    struct Query {
        int l, r;
        ll p;
    };

    void solve() {
        vector<Query> qs(q);
        for (int i = 0; i < q; i++)
            cin >> qs[i].l >> qs[i].r >> qs[i].p;

        vector<int> idx(q);
        iota(all(idx), 0);
        sort(all(idx), [&](int a, int p) {
            if (qs[a].l != qs[p].l)
                return qs[a].l < qs[p].l;
            return qs[a].r < qs[p].r;
        });

        for (int t = 1; t < q; t++) {
            Query& prev = qs[idx[t - 1]];
            Query& cur = qs[idx[t]];
            if (cur.l <= prev.r) {
                cout << -1 << '\n';
                return;
            }
        }

        vector<ll> a(n + 1, 1e9);
        for (int i = 0; i < q; i++) {
            int id = idx[i];
            for (int p = qs[id].l; p <= qs[id].r; ++p)
                a[p] = qs[id].p;
        }
        for (int i = 1; i <= N; i++)
            cout << a[i] << ' ';
    }
}

namespace sub34 {
    bool check() {
        return true;
    }
    void solve() {
        vector<array<int, 3>> query(q);
        set<int> nused, used;
        vector<int> ans(n + 1);

        for (int i = 1; i <= n; i++)
            nused.insert(i);

        for (int i = 0; i < q; i++) {
            int l, r, p;
            cin >> l >> r >> p;
            query[i] = {p, l, r};
        }

        sort(all(query));
        reverse(all(query));

        int prev = -1;
        for (auto [p, l, r] : query) {
            if (p != prev) {
                prev = p;
                used.clear();
            }

            auto itr = nused.lower_bound(l);
            if (itr == nused.end() || *itr > r) {
                if (used.size() == 0) {
                    cout << "-1" << '\n';
                    return;
                }
            } else {
                while (itr != nused.end() && *itr <= r) {
                    ans[*itr] = p;
                    used.insert(*itr);
                    itr = nused.erase(itr);
                }
            }
        }

        for (auto i : nused)
            ans[i] = int(1e9);

        for (int i = 1; i <= n; i++)
            cout << ans[i] << " \n"[i == n];
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= q; i++)
        cin >> l[i] >> r[i] >> p[i];

    if (sub1::check())
        return sub1::solve(), 0;
    if (sub2::check())
        return sub2::solve(), 0;
    if (sub34::check())
        return sub34::solve(), 0;

    return 0;
}
0