結果
問題 | No.3134 二分探索木 |
ユーザー |
|
提出日時 | 2025-05-02 21:56:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 103 ms / 2,000 ms |
コード長 | 1,083 bytes |
コンパイル時間 | 2,194 ms |
コンパイル使用メモリ | 200,572 KB |
実行使用メモリ | 10,948 KB |
最終ジャッジ日時 | 2025-05-02 21:56:26 |
合計ジャッジ時間 | 4,482 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 15 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:17:42: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 17 | for (int i = 1; i < n + 1; i++) scanf("%d", w + i); | ~~~~~^~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; typedef long long ll; const int N = 2000086, MOD = 998244353, INF = 0x3f3f3f3f; ll res; int n, m, cnt, w[N]; pii ans[N]; typedef pair<pii, int> piii; int main() { cin >> n; for (int i = 1; i < n + 1; i++) scanf("%d", w + i); set<piii> st = {{{1, n}, -1}}; for (int i = 1; i < n + 1; i++) { auto u = st.upper_bound({{w[i], INF}, INF}); // printf("%d %d\n", st.begin()->first.first, st.begin()->first.second); // if (u == st.begin()) { // exit(0); // } assert(u != st.begin()); u--; ans[i].first = u->second + 1; int l = u->first.first, r = u->first.second; ans[i].second = r - l; st.erase(u); if (w[i] - l >= 1) st.insert({{l, w[i] - 1}, ans[i].first}); if (r - w[i] >= 1) st.insert({{w[i] + 1, r}, ans[i].first}); } for (int i = 1; i < n + 1; i++) printf("%d ", ans[i].first); puts(""); for (int i = 1; i < n + 1; i++) printf("%d ", ans[i].second); return 0; }