結果
問題 | No.2220 Range Insert & Point Mex |
ユーザー |
|
提出日時 | 2023-02-17 23:51:12 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 131 ms / 2,000 ms |
コード長 | 1,966 bytes |
コンパイル時間 | 10,845 ms |
コンパイル使用メモリ | 295,104 KB |
最終ジャッジ日時 | 2025-02-10 18:25:05 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#ifdef LOCAL#include <local.hpp>#else#pragma GCC optimize("O3,unroll-loops")#pragma GCC target("avx2")#include <bits/stdc++.h>#define debug(...) (static_cast<void>(0))#define postprocess() (static_cast<void>(0))#endif// #include "atcoder/dsu.hpp"// #include "atcoder/modint.hpp"// using mint = atcoder::modint998244353;// using mint = atcoder::modint1000000007;using namespace std;using ll = long long;using ld = long double;void solve([[maybe_unused]] int test) {// 1: l_i, a_i// 2: x_i, i// 3: r_i, a_ivector<tuple<int, int, int>> queries;int N;cin >> N;for (int i = 0; i < N; i++) {int l, r, a;cin >> l >> r >> a;if (a <= N) {queries.push_back({l, 1, a});queries.push_back({r, 3, a});}}int Q;cin >> Q;for (int i = 0; i < Q; i++) {int x;cin >> x;queries.push_back({x, 2, i});}sort(queries.begin(), queries.end());optional<int> ans[Q];int num[N + 1];set<int> not_included;for (int i = 0; i <= N; i++) {num[i] = 0;not_included.insert(i);}for (auto&& query : queries) {int type = get<1>(query);if (type == 1) {int l, a;tie(l, ignore, a) = query;num[a] += 1;not_included.erase(a);}if (type == 3) {int r, a;tie(r, ignore, a) = query;num[a] -= 1;if (num[a] == 0) not_included.insert(a);}if (type == 2) {int x, i;tie(x, ignore, i) = query;ans[i] = *not_included.begin();}}for (int i = 0; i < Q; i++) {cout << ans[i].value_or(-1) << '\n';}}int main() {ios::sync_with_stdio(false), cin.tie(nullptr);int t = 1;// cin >> t;for (int _t = 1; _t <= t; _t++) solve(_t);postprocess();}