結果
問題 | No.2220 Range Insert & Point Mex |
ユーザー | SSRS |
提出日時 | 2023-02-17 21:31:35 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 575 ms / 2,000 ms |
コード長 | 2,062 bytes |
コンパイル時間 | 1,889 ms |
コンパイル使用メモリ | 181,112 KB |
実行使用メモリ | 17,556 KB |
最終ジャッジ日時 | 2023-09-28 17:59:12 |
合計ジャッジ時間 | 12,835 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,376 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 1 ms
4,376 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 2 ms
4,380 KB |
testcase_11 | AC | 2 ms
4,376 KB |
testcase_12 | AC | 1 ms
4,376 KB |
testcase_13 | AC | 385 ms
14,736 KB |
testcase_14 | AC | 390 ms
14,660 KB |
testcase_15 | AC | 386 ms
14,804 KB |
testcase_16 | AC | 389 ms
14,600 KB |
testcase_17 | AC | 388 ms
14,672 KB |
testcase_18 | AC | 381 ms
14,668 KB |
testcase_19 | AC | 388 ms
14,732 KB |
testcase_20 | AC | 565 ms
16,980 KB |
testcase_21 | AC | 563 ms
17,044 KB |
testcase_22 | AC | 575 ms
16,992 KB |
testcase_23 | AC | 318 ms
17,556 KB |
testcase_24 | AC | 231 ms
13,516 KB |
testcase_25 | AC | 255 ms
14,216 KB |
testcase_26 | AC | 285 ms
14,912 KB |
testcase_27 | AC | 127 ms
9,740 KB |
testcase_28 | AC | 155 ms
8,076 KB |
testcase_29 | AC | 170 ms
8,084 KB |
testcase_30 | AC | 173 ms
8,208 KB |
testcase_31 | AC | 274 ms
14,972 KB |
testcase_32 | AC | 222 ms
10,972 KB |
testcase_33 | AC | 232 ms
11,060 KB |
testcase_34 | AC | 282 ms
11,736 KB |
testcase_35 | AC | 297 ms
11,896 KB |
testcase_36 | AC | 323 ms
14,920 KB |
testcase_37 | AC | 338 ms
14,860 KB |
testcase_38 | AC | 288 ms
15,172 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; const int INF = 1100000000; struct mex_set{ set<pair<int, int>> st; mex_set(){ st.insert(make_pair(-2, -2)); st.insert(make_pair(INF, INF)); } void insert(int x){ int L = x, R = x; auto itr1 = st.lower_bound(make_pair(x, 0)); if ((*itr1).first == x + 1){ R = (*itr1).second; st.erase(itr1); } auto itr2 = prev(st.lower_bound(make_pair(x, 0))); if ((*itr2).second == x - 1){ L = (*itr2).first; st.erase(itr2); } st.insert(make_pair(L, R)); } void erase(int x){ auto itr = prev(st.lower_bound(make_pair(x, INF))); int L = (*itr).first; int R = (*itr).second; st.erase(itr); if (L < x){ st.insert(make_pair(L, x - 1)); } if (x < R){ st.insert(make_pair(x + 1, R)); } } int mex(){ auto itr = st.lower_bound(make_pair(0, 0)); if ((*itr).first > 0){ return 0; } else { return (*itr).second + 1; } } }; struct mex_multiset{ multiset<int> st; mex_set S; mex_multiset(){ } void insert(int x){ if (st.find(x) == st.end()){ S.insert(x); } st.insert(x); } void erase(int x){ st.erase(st.find(x)); if (st.find(x) == st.end()){ S.erase(x); } } int mex(){ return S.mex(); } }; int main(){ int N; cin >> N; vector<int> l(N), r(N), a(N); for (int i = 0; i < N; i++){ cin >> l[i] >> r[i] >> a[i]; l[i]--; } int Q; cin >> Q; vector<int> x(Q); for (int i = 0; i < Q; i++){ cin >> x[i]; x[i]--; } for (int i = 0; i < N; i++){ l[i] = lower_bound(x.begin(), x.end(), l[i]) - x.begin(); r[i] = lower_bound(x.begin(), x.end(), r[i]) - x.begin(); } vector<vector<int>> add(Q + 1), sub(Q + 1); for (int i = 0; i < N; i++){ add[l[i]].push_back(a[i]); sub[r[i]].push_back(a[i]); } mex_multiset st; for (int i = 0; i < Q; i++){ for (int j : add[i]){ st.insert(j); } for (int j : sub[i]){ st.erase(j); } cout << st.mex() << endl; } }