結果

問題 No.2292 Interval Union Find
ユーザー KumaTachiRenKumaTachiRen
提出日時 2023-05-05 22:32:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 216 ms / 5,000 ms
コード長 3,317 bytes
コンパイル時間 4,265 ms
コンパイル使用メモリ 259,172 KB
最終ジャッジ日時 2025-02-12 18:48:59
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
struct Fast
{
Fast()
{
std::cin.tie(0);
ios::sync_with_stdio(false);
}
} fast;
#define rep(i, a, b) for (int i = (a); i < (int)(b); i++)
#define rrep(i, a, b) for (int i = (int)(b)-1; i >= (a); i--)
#define ll long long
template <typename T>
bool chmax(T &a, const T &b)
{
if (a < b)
{
a = b;
return true;
}
return false;
}
template <typename T>
bool chmin(T &a, const T &b)
{
if (a > b)
{
a = b;
return true;
}
return false;
}
// https://satanic0258.github.io/snippets/data-structure/SegmentMap.html
// Description: set(map)O(log)
// #### attention! : [l, r] ( include r, not [l, r) )
class SegmentMap : public std::map<signed, signed>
{
private:
bool flagToMergeAdjacentSegment;
public:
// if merge [l, c] and [c+1, r], set flagToMergeAdjacentSegment to true
SegmentMap(bool flagToMergeAdjacentSegment) : flagToMergeAdjacentSegment(flagToMergeAdjacentSegment) {}
// __exist -> iterator pair(l, r) (contain p)
// noexist -> map.end()
auto get(signed p) const
{
auto it = upper_bound(p);
if (it == begin() || (--it)->second < p)
return end();
return it;
}
// insert segment [l, r]
void insert(signed l, signed r)
{
auto itl = upper_bound(l), itr = upper_bound(r + flagToMergeAdjacentSegment);
if (itl != begin())
{
if ((--itl)->second < l - flagToMergeAdjacentSegment)
++itl;
}
if (itl != itr)
{
l = std::min(l, itl->first);
r = std::max(r, std::prev(itr)->second);
erase(itl, itr);
}
(*this)[l] = r;
}
// remove segment [l, r]
void remove(signed l, signed r)
{
auto itl = upper_bound(l), itr = upper_bound(r);
if (itl != begin())
{
if ((--itl)->second < l)
++itl;
}
if (itl == itr)
return;
int tl = std::min(l, itl->first), tr = std::max(r, std::prev(itr)->second);
erase(itl, itr);
if (tl < l)
(*this)[tl] = l - 1;
if (r < tr)
(*this)[r + 1] = tr;
}
// Is p and q in same segment?
bool same(signed p, signed q) const
{
const auto &&it = get(p);
return it != end() && it->first <= q && q <= it->second;
}
bool contains(signed x) const
{
const auto &&it = get(x);
return it != end() && it->first <= x && x <= it->second;
}
};
int main()
{
int n, q;
cin >> n >> q;
SegmentMap s(false);
while (q--)
{
int type;
cin >> type;
if (type == 1)
{
int l, r;
cin >> l >> r;
l--;
r--;
s.insert(l, r);
}
if (type == 2)
{
int l, r;
cin >> l >> r;
l--;
r--;
s.remove(l + 1, r - 1);
}
if (type == 3)
{
int u, v;
cin >> u >> v;
u--;
v--;
int ans = -1;
if (u == v)
{
ans = 1;
}
else
{
ans = s.same(u, v) ? 1 : 0;
}
cout << ans << "\n";
}
if (type == 4)
{
int v;
cin >> v;
v--;
if (s.contains(v))
{
auto it = s.get(v);
cout << (it->second - it->first + 1) << "\n";
}
else
{
cout << 1 << "\n";
}
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0