結果
問題 | No.1675 Strange Minimum Query |
ユーザー |
![]() |
提出日時 | 2020-05-13 17:26:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 442 ms / 2,000 ms |
コード長 | 2,541 bytes |
コンパイル時間 | 1,977 ms |
コンパイル使用メモリ | 184,680 KB |
実行使用メモリ | 18,948 KB |
最終ジャッジ日時 | 2024-06-11 21:30:58 |
合計ジャッジ時間 | 13,452 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h> using namespace std; void checker1(int &N, int &Q) { assert(1 <= N && N <= 2e5); assert(1 <= Q && Q <= 2e5); } void checker2(int &l, int &r, int &B, int &N) { assert(1 <= l && l <= r && r <= N); assert(1 <= B && B <= 1e9); } // Segment-Tree struct SegmentTree { int n; vector<int> dat; SegmentTree(vector<int> &v) { n = 1; while (n < v.size()) n *= 2; dat.resize(2 * n - 1, 1e9); for (int i = 0; i < v.size(); i++) { dat.at(i + n - 1) = v.at(i); } for (int i = n - 2; i >= 0; i--) { dat.at(i) = min(dat.at(2 * i + 1), dat.at(2 * i + 2)); } } // [a, b)の最小値 // k:ノードの番号 [l, r)がkに対応づいている // query(a, b, 0, 0, n)と呼ぶ int query(int a, int b, int k = 0, int l = 0, int r = -1) { if (r == -1) r = n; if (r <= a || b <= l) return 1e9; if (a <= l && r <= b) return dat[k]; else { int vl = query(a, b, 2 * k + 1, l, (l + r) / 2); int vr = query(a, b, 2 * k + 2, (l + r) / 2, r); return min(vl, vr); } } }; int main() { // 入力 int N, Q; cin >> N >> Q; checker1(N, Q); vector<int> l(Q), r(Q), B(Q); for (int i = 0; i < Q; i++) { cin >> l.at(i) >> r.at(i) >> B.at(i); checker2(l.at(i), r.at(i), B.at(i), N); // 0-indexedに変換 l.at(i)--; r.at(i)--; } // 過剰な入力の検出 { int tmp; while (cin >> tmp) { assert(false); } } // 構築 vector<pair<int, int>> vl, vr; for (int i = 0; i < Q; i++) { vl.emplace_back(make_pair(l.at(i), B.at(i))); vr.emplace_back(make_pair(r.at(i), B.at(i))); } sort(vl.begin(), vl.end()); sort(vr.begin(), vr.end()); int vl_it = 0, vr_it = 0; multiset<int> ms; vector<int> ans(N, 1e9); for (int i = 0; i < N; i++) { while (vl_it < vl.size() && vl.at(vl_it).first == i) { ms.insert(vl.at(vl_it).second); vl_it++; } if (!ms.empty()) { ans.at(i) = *ms.rbegin(); // Bの値が最も大きいものを使う } while (vr_it < vr.size() && vr.at(vr_it).first == i) { ms.erase(ms.find(vr.at(vr_it).second)); vr_it++; } } // 条件を満たすか判定 SegmentTree ST(ans); bool flag = true; for (int i = 0; i < Q; i++) { if (ST.query(l.at(i), r.at(i) + 1) != B.at(i)) flag = false; } // 出力 if (flag) { for (int i = 0; i < N; i++) { if (i) cout << " "; cout << ans.at(i); } cout << '\n'; } else { cout << "-1\n"; } return 0; }