結果

問題 No.1675 Strange Minimum Query
コンテスト
ユーザー vjudge1
提出日時 2025-12-08 18:33:55
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 207 ms / 2,000 ms
コード長 1,320 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,061 ms
コンパイル使用メモリ 209,040 KB
実行使用メモリ 16,000 KB
最終ジャッジ日時 2025-12-08 18:34:08
合計ジャッジ時間 12,353 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:12:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   12 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:24:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   24 |         scanf("%d %d %d", &l, &r, &b);  // gi? nguy�n 1-based
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

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

#define endl "\n"
#define all(v) v.begin(), v.end()

const int N = 2e5 + 10;

int n, q;

int main() {
    scanf("%d %d", &n, &q);
    vector<array<int, 3>> query(q);
    set<int> unused;
    set<int> used;
    vector<int> ans(n + 1);

    // unused = {1..n}
    for (int i = 1; i <= n; i++)
        unused.insert(i);

    for (int i = 0; i < q; i++) {
        int l, r, b;
        scanf("%d %d %d", &l, &r, &b);  // gi? nguyn 1-based
        query[i] = {b, l, r};
    }

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

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

        auto itr = unused.lower_bound(l);
        if (itr == unused.end() || *itr > r) {
            // khng c ph?n t? unused trong ?o?n [l, r]
            if (used.size() == 0) {
                cout << "-1" << endl;
                return 0;
            }
        } else {
            while (itr != unused.end() && *itr <= r) {
                ans[*itr] = b;
                used.insert(*itr);
                itr = unused.erase(itr);
            }
        }
    }

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

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

    return 0;
}
0