結果
問題 | No.2220 Range Insert & Point Mex |
ユーザー |
👑 ![]() |
提出日時 | 2023-02-17 21:40:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 73 ms / 2,000 ms |
コード長 | 3,971 bytes |
コンパイル時間 | 1,042 ms |
コンパイル使用メモリ | 89,268 KB |
最終ジャッジ日時 | 2025-02-10 16:32:56 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#line 1 "Main.cpp" #include <iostream> #include <string> #include <vector> #include <algorithm> #include <atcoder/modint> #line 2 "nachia\\set\\word-size-tree.hpp" #line 5 "nachia\\set\\word-size-tree.hpp" namespace nachia{ struct WordsizeTree{ using Word = unsigned long long; static constexpr int W = 64; int N; std::vector<std::vector<Word>> A; static int highBit(Word x){ if(x == 0) return 0; return W-1 - __builtin_clzll(x); } static int lowBit(Word x){ if(x == 0) return W; return __builtin_ctzll(x); } WordsizeTree(unsigned int length){ N = length; int n = length; do { std::vector<Word> a(n/W+1,0); A.emplace_back(std::move(a)); n /= W; } while(n); } WordsizeTree(const std::string& binStr = ""){ N = binStr.size(); int n = N; { std::vector<Word> a(n/W+1); for(int i=0; i<n; i++) if(binStr[i] == '1'){ a[i/W] |= (Word)1 << (i%W); } A.emplace_back(std::move(a)); n /= W; } while(n){ std::vector<Word> a(n/W+1,0); for(int i=0; i<=n; i++){ if(A.back()[i]) a[i/W] |= (Word)1 << (i%W); } A.emplace_back(std::move(a)); n /= W; } } void insert(int x){ for(auto& a : A){ a[x/W] |= (Word)1 << (x % W); x /= W; } } void erase(int x){ for(auto& a : A){ a[x/W] &= ~((Word)1 << (x % W)); if(a[x/W]) return; x /= W; } } int count(int x) const { return (int)((A[0][x/W] >> (x%W)) & 1); } int noLessThan(int x) const { int d = 0, i = x; while(true){ if(d >= (int)A.size()) return -1; if(i/W >= (int)A[d].size()) return -1; Word m = A[d][i/W] & ((~(Word)0) << (i%W)); if(!m){ d++; i /= W; i++; } else{ int to = lowBit(m); i = i/W*W + to; if(d == 0) break; i *= W; d--; } } return i; } int noGreaterThan(int x) const { int d = 0, i = x; while(true){ if(i < 0) return -1; if(d >= (int)A.size()) return -1; Word m = A[d][i/W] & ~((~(Word)1) << (i%W)); if(!m){ d++; i /= W; i--; } else{ int to = highBit(m); i = i/W*W + to; if(d == 0) break; i *= W; i += W-1; d--; } } return i; } }; } // namespace nachia #line 7 "Main.cpp" using namespace std; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<1000000007>; int main(){ int N; cin >> N; vector<pair<int, int>> Ins, Rem; rep(i,N){ int l, r, a; cin >> l >> r >> a; l--; if(a > N) continue; Ins.emplace_back(l, a); Rem.emplace_back(r, a); } sort(Ins.begin(), Ins.end()); sort(Rem.begin(), Rem.end()); int Q; cin >> Q; vector<int> T(Q); rep(i,Q) cin >> T[i]; nachia::WordsizeTree rex(string(N+1, '1')); vector<int> cnt(N+1); int ii = 0; int ir = 0; rep(i,Q){ while(ii < (int)Ins.size() && Ins[ii].first < T[i]) if(cnt[Ins[ii++].second]++ == 0) rex.erase(Ins[ii-1].second); while(ir < (int)Rem.size() && Rem[ir].first < T[i]) if(--cnt[Rem[ir++].second] == 0) rex.insert(Rem[ir-1].second); cout << rex.noLessThan(0) << '\n'; } return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;