結果
| 問題 | No.2292 Interval Union Find |
| ユーザー |
 miie
|
| 提出日時 | 2024-11-08 21:03:52 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 6,805 bytes |
| コンパイル時間 | 4,962 ms |
| コンパイル使用メモリ | 334,424 KB |
| 最終ジャッジ日時 | 2025-01-28 23:27:10 |
| 合計ジャッジ時間 | 8,927 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
In file included from /usr/include/c++/13/string:43,
from /usr/include/c++/13/bitset:52,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
from main.cpp:4:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::__cxx11::basic_string<char>::_Alloc_hider::~_Alloc_hider()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = char]’: target specific option mismatch
184 | ~allocator() _GLIBCXX_NOTHROW { }
| ^
In file included from /usr/include/c++/13/string:54:
/usr/include/c++/13/bits/basic_string.h:181:14: note: called from here
181 | struct _Alloc_hider : allocator_type // TODO check __is_final
| ^~~~~~~~~~~~
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <bits/stdc++.h>using namespace std;#include <atcoder/all>using namespace atcoder;// 数値型using mint = modint998244353;using ll = long long;using ull = unsigned long long;using ld = long double;using P = pair<int,int>;using Pll = pair<ll, ll>;using Pli = pair<ll, int>;using Pil = pair<int, ll>;// vector関連using vi = vector<int>;using vvi = vector<vi>;using vvvi = vector<vvi>;using vll = vector<ll>;using vvll = vector<vll>;using vvvll = vector<vvll>;template<typename T>using vc = vector<T>;template<typename T>using vvc = vector<vc<T>>;template<typename T>using vvvc = vector<vvc<T>>;template<typename T>using vvvvc = vector<vvvc<T>>;// priority_queuetemplate<typename T>using pq = priority_queue<T>;template<typename T>using pqg = priority_queue<T, vc<T>, greater<T>>;#define rep(i, n) for(int i = 0; i < (int)(n); i++)#define FOR(i, a, b) for(int i = a; i < (int)(b); i++)#define all(a) (a).begin(),(a).end()#define rall(a) (a).rbegin(),(a).rend()#define MIN(vec) *min_element(vec)#define MAX(vec) *max_element(vec)#define next_perm(vec) (vec).begin(), (vec).end()#define UNIQUE(vec) vec.erase(unique(vec.begin(), vec.end()), vec.end())#define el "\n"#define Yes cout << "Yes" << el#define No cout << "No" << el#define YES cout << "YES" << el#define NO cout << "NO" << el#define minus1 cout << -1 << el#define EPS 1e-8#define Equal(a, b) (fabs((a)-(b)) < EPS)#define dbg(x) cerr << #x << "=" << x << el// 定数const string abc = "abcdefghijklmnopqrstuvwxyz";const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";constexpr int INF = 1001001001;constexpr ll LINF = 1001001001001001001ll;constexpr int DX[] = {1, 0, -1, 0};constexpr int DY[] = {0, 1, 0, -1};constexpr int DX8[] = {1, 0, -1, 0, 1, 1, -1, -1};constexpr int DY8[] = {0, 1, 0, -1, 1, -1, 1, -1};template<typename T1, typename T2>ostream &operator<< (ostream &os, pair<T1, T2> p) {os << "{" << p.first << "," << p.second << "}";return os;}template<typename T>ostream &operator<< (ostream &os, vc<T> &vec) {int sz = vec.size();rep(i, sz){os << vec[i] << (i==sz-1?"":" ");}return os;}istream &operator>> (istream &is, mint &a) {ll x;is >> x;a = x;return is;}template<typename T1, typename T2>istream &operator>> (istream &is, pair<T1, T2> &p) {is >> p.first >> p.second;return is;}template<typename T>istream &operator>> (istream &is, vc<T> &vec) {int sz = vec.size();rep(i, sz) { is >> vec[i]; }return is;}/// @brief aとｂの最大値をaに格納。更新があったかbool値を返す/// @tparam T1/// @tparam T2/// @param a/// @param b/// @return booltemplate<typename T1, typename T2>inline bool chmax(T1 &a, T2 b){bool ret = a<b;if(ret) a = b;return ret;}/// @brief aとｂの最小値をaに格納。更新があったかbool値を返す/// @tparam T1/// @tparam T2/// @param a/// @param b/// @return booltemplate<typename T1, typename T2>inline bool chmin(T1 &a, T2 b){bool ret = a>b;if(ret) {a = b;}return ret;}inline void YesNo(bool flag){if(flag) {Yes;}else {No;}return;}inline void YESNO(bool flag){if(flag) {YES;}else {NO;}return;}inline bool outof(ll x, ll xlim){return (x<0 || x>=xlim);}template<typename T>inline T sqnorm(T x, T y){return x*x+y*y;}/// @brief char->int/// @param c/// @return intinline int ctoi(char c){return c-'0';}/// @brief xを素因数分解/// @param x/// @return vector<Pli>, 素因数の昇順に {p, cnt}vector<Pli> prime_fact(ll x){vector<Pli> ret;for(ll i=2; i*i<=x; i++){if(x%i == 0){ret.emplace_back(i, 0);while(x%i == 0){ret.back().second++;x /= i;}}}if(x != 1) ret.emplace_back(x, 1);return ret;}/// @brief xの約数列挙/// @param x/// @return vll, 約数の昇順vll divisor_enum(ll x){vector<ll> ret;for(ll i=1; i*i<=x; i++){if(x%i == 0){ret.push_back(x/i);ret.push_back(i);}}sort(all(ret));UNIQUE(ret);return ret;}/// @brief 繰り返し二乗法。/// @tparam T/// @param x/// @param k/// @param op/// @param e/// @returntemplate<typename T>T pow_t(T x, ll k, T (*op)(T, T), T (*e)()){T ret = e();while(k){if(k&1) ret *= x;x *= x;k >>= 1;}return ret;}ll powll(ll x, ll k){return pow_t<ll>(x, k, [](ll a, ll b) -> ll{return a*b;}, []() -> ll{return 1;});}inline int pop_cnt(ll x) { return __builtin_popcountll(x); }inline int top_bit(ll x) { return (x==0?-1:63-__builtin_clzll(x));}void main2();int main(){ios::sync_with_stdio(false);std::cin.tie(nullptr);main2();}void main2(){int n, q;cin >> n >> q;set<P> st;auto add = [&](int l, int r) -> void{while(1){auto it = st.upper_bound({l, n+1});if(it == st.end()) break;if(it->first >= r) break;chmax(r, it->second);st.erase(it);}auto it = st.upper_bound({l, n+1});if(it == st.begin() || prev(it)->second <= l) st.insert({l, r});else{l = prev(it)->first;chmax(r, prev(it)->second);st.erase(prev(it));st.insert({l, r});}return;};auto del = [&](int l, int r) -> void{while(1){auto it = st.lower_bound({l, -1});if(it == st.end() || it->first >= r) break;int nr = it->second;st.erase(it);if(nr > r) st.insert({r, nr});}auto it = st.lower_bound({l, -1});if(it != st.begin() && prev(it)->second > l){int nl = prev(it)->first;int nr = prev(it)->second;st.erase(prev(it));if(nl < l) st.insert({nl, l});if(r < nr) st.insert({r, nr});}return;};auto same = [&](int u, int v) -> bool{auto it = st.upper_bound({u, INF});if(it == st.begin() || prev(it)->second <= v) return u == v;return true;};auto size = [&](int x) -> int{auto it = st.upper_bound({x, INF});if(it == st.begin() || prev(it)->second <= x) return 1;return prev(it)->second - prev(it)->first;};rep(i, q){int t;cin >> t;if(t == 1){int l, r;cin >> l >> r;add(l-1, r);}if(t == 2){int l, r;cin >> l >> r;del(l, r-1);}if(t == 3){int u, v;cin >> u >> v;u--;v--;if(u > v) swap(u, v);cout << (same(u, v)?1:0) << el;}if(t == 4){int v;cin >> v;v--;cout << size(v) << el;}}}