結果

問題 No.1675 Strange Minimum Query
ユーザー hanyu
提出日時 2021-08-21 17:19:57
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,064 bytes
コンパイル時間 2,450 ms
コンパイル使用メモリ 210,536 KB
最終ジャッジ日時 2025-01-24 01:24:02
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int main() {
  int n, q;
  cin >> n >> q;
  
  vector<vector<int>> query(q, vector<int>(3));
  for (int i = 0; i < q; i++) {
    cin >> query.at(i).at(1) >> query.at(i).at(2) >> query.at(i).at(0);
    query.at(i).at(1)--;
    query.at(i).at(2)--;
  }
  
  sort(query.rbegin(), query.rend());
  
  vector<int> a(n, 1e9);
  set<int> st, use;
  for (int i = 0; i < n; i++) st.insert(i);
  
  bool ok = true;
  for (int i = 0; i < q; i++) {
    if (i == 0 || query.at(i).at(0) != query.at(i - 1).at(0)) use.clear();
    auto it = st.lower_bound(query.at(i).at(1));
    if (it == st.end() || *it > query.at(i).at(2)) {
      auto it2 = use.lower_bound(query.at(i).at(1));
      if (it2 == use.end() || *it2 > query.at(i).at(2)) ok = false;
    }
    else {
      a.at(*it) = query.at(i).at(0);
      use.insert(*it);
      st.erase(it);
    }
  }
  
  if (ok) {
    for (int i = 0; i < n; i++) {
      if (i) cout << " ";
      cout << a.at(i);
    }
    cout << '\n';
  }
  else {
    cout << -1 << '\n';
  }
}
0