結果
問題 | No.1675 Strange Minimum Query |
ユーザー | hanyu |
提出日時 | 2020-05-13 17:26:04 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 435 ms / 2,000 ms |
コード長 | 2,541 bytes |
コンパイル時間 | 3,247 ms |
コンパイル使用メモリ | 182,564 KB |
実行使用メモリ | 18,868 KB |
最終ジャッジ日時 | 2023-09-02 14:59:05 |
合計ジャッジ時間 | 14,301 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 341 ms
11,456 KB |
testcase_04 | AC | 294 ms
10,660 KB |
testcase_05 | AC | 21 ms
5,152 KB |
testcase_06 | AC | 432 ms
13,260 KB |
testcase_07 | AC | 435 ms
13,472 KB |
testcase_08 | AC | 2 ms
4,376 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 116 ms
7,752 KB |
testcase_11 | AC | 25 ms
6,184 KB |
testcase_12 | AC | 129 ms
7,840 KB |
testcase_13 | AC | 292 ms
18,868 KB |
testcase_14 | AC | 323 ms
18,768 KB |
testcase_15 | AC | 297 ms
18,848 KB |
testcase_16 | AC | 1 ms
4,376 KB |
testcase_17 | AC | 50 ms
5,060 KB |
testcase_18 | AC | 75 ms
6,128 KB |
testcase_19 | AC | 87 ms
7,760 KB |
testcase_20 | AC | 234 ms
12,244 KB |
testcase_21 | AC | 202 ms
10,960 KB |
testcase_22 | AC | 272 ms
12,992 KB |
testcase_23 | AC | 236 ms
10,168 KB |
testcase_24 | AC | 197 ms
10,044 KB |
testcase_25 | AC | 151 ms
7,684 KB |
testcase_26 | AC | 64 ms
6,104 KB |
testcase_27 | AC | 176 ms
10,240 KB |
testcase_28 | AC | 83 ms
7,676 KB |
testcase_29 | AC | 51 ms
6,532 KB |
testcase_30 | AC | 61 ms
5,884 KB |
testcase_31 | AC | 308 ms
12,688 KB |
testcase_32 | AC | 375 ms
14,092 KB |
testcase_33 | AC | 373 ms
16,112 KB |
testcase_34 | AC | 383 ms
16,392 KB |
testcase_35 | AC | 346 ms
11,620 KB |
testcase_36 | AC | 341 ms
11,276 KB |
ソースコード
#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; }