結果

問題 No.2292 Interval Union Find
コンテスト
ユーザー kotatsugame
提出日時 2023-05-05 21:43:58
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 213 ms / 5,000 ms
コード長 1,638 bytes
コンパイル時間 841 ms
コンパイル使用メモリ 78,828 KB
実行使用メモリ 12,928 KB
最終ジャッジ日時 2024-11-23 06:42:30
合計ジャッジ時間 10,075 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<map>
using namespace std;
int N,Q;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N>>Q;
	map<int,int>S;
	for(;Q--;)
	{
		int op;cin>>op;
		if(op==1)
		{
			int L,R;cin>>L>>R;
			auto it=S.lower_bound(L);
			if(it!=S.begin())
			{
				it--;
				if(it->second>=L)
				{
					L=it->first;
					R=max(R,it->second);
					it=S.erase(it);
				}
				else it++;
			}
			while(it!=S.end()&&it->first<=R)
			{
				R=max(R,it->second);
				it=S.erase(it);
			}
			S.insert(it,make_pair(L,R));
		}
		else if(op==2)
		{
			int L,R;cin>>L>>R;
			auto it=S.lower_bound(L);
			if(it!=S.begin())
			{
				it--;
				if(it->second>R)
				{
					pair<int,int>p=*it;
					it=S.erase(it);
					it=S.insert(it,make_pair(p.first,L));
					it++;
					S.insert(it,make_pair(R,p.second));
					continue;
				}
				if(it->second>L)
				{
					pair<int,int>p=*it;
					it=S.erase(it);
					p.second=L;
					it=S.insert(it,p);
					it++;
				}
				else it++;
			}
			while(it!=S.end()&&it->first<=R)
			{
				pair<int,int>p=*it;
				it=S.erase(it);
				p.first=R;
				if(p.first<p.second)
				{
					S.insert(it,p);
					break;
				}
			}
		}
		else if(op==3)
		{
			int u,v;cin>>u>>v;
			if(u>v)swap(u,v);
			if(u==v)
			{
				cout<<"1\n";
				continue;
			}
			auto it=S.upper_bound(u);
			if(it!=S.begin())
			{
				it--;
				if(it->second>=v)cout<<"1\n";
				else cout<<"0\n";
			}
			else cout<<"0\n";
		}
		else
		{
			int u;cin>>u;
			auto it=S.upper_bound(u);
			int ans=1;
			if(it!=S.begin())
			{
				it--;
				if(it->second>=u)
				{
					ans=it->second-it->first+1;
				}
			}
			cout<<ans<<"\n";
		}
	}
}
0