#866283 (C++14) No.2292 Interval Union Find

• 問題: No.2292 Interval Union Find
• ユーザー: kotatsugame
• 提出日時: 2023-05-05 21:43:58
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 146 ms / 5,000 ms
• コード長: 1,638 bytes
• コンパイル時間: 703 ms
• コンパイル使用メモリ: 77,568 KB
• 実行使用メモリ: 12,928 KB
• 最終ジャッジ日時: 2024-05-02 15:42:46
• 合計ジャッジ時間: 7,927 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	54 ms; 5,376 KB
testcase_05	AC	78 ms; 5,376 KB
testcase_06	AC	53 ms; 5,376 KB
testcase_07	AC	73 ms; 5,376 KB
testcase_08	AC	79 ms; 5,376 KB
testcase_09	AC	80 ms; 5,376 KB
testcase_10	AC	73 ms; 5,376 KB
testcase_11	AC	72 ms; 5,376 KB
testcase_12	AC	84 ms; 5,376 KB
testcase_13	AC	65 ms; 5,376 KB
testcase_14	AC	66 ms; 5,376 KB
testcase_15	AC	69 ms; 5,376 KB
testcase_16	AC	67 ms; 5,376 KB
testcase_17	AC	77 ms; 5,376 KB
testcase_18	AC	111 ms; 12,928 KB
testcase_19	AC	140 ms; 12,672 KB
testcase_20	AC	146 ms; 12,928 KB
testcase_21	AC	122 ms; 8,832 KB
testcase_22	AC	121 ms; 8,960 KB
testcase_23	AC	128 ms; 8,832 KB
testcase_24	AC	121 ms; 8,960 KB
testcase_25	AC	122 ms; 8,832 KB
testcase_26	AC	123 ms; 8,832 KB
testcase_27	AC	122 ms; 8,960 KB
testcase_28	AC	118 ms; 8,832 KB
testcase_29	AC	121 ms; 8,832 KB
testcase_30	AC	122 ms; 8,832 KB
testcase_31	AC	125 ms; 8,832 KB
testcase_32	AC	133 ms; 8,832 KB
testcase_33	AC	135 ms; 8,832 KB
testcase_34	AC	139 ms; 8,832 KB
testcase_35	AC	123 ms; 8,832 KB
testcase_36	AC	126 ms; 8,832 KB
testcase_37	AC	123 ms; 8,832 KB
testcase_38	AC	120 ms; 8,832 KB
testcase_39	AC	119 ms; 8,832 KB
testcase_40	AC	124 ms; 8,960 KB
testcase_41	AC	39 ms; 5,376 KB
testcase_42	AC	40 ms; 5,376 KB
testcase_43	AC	43 ms; 5,376 KB
testcase_44	AC	55 ms; 5,376 KB
testcase_45	AC	53 ms; 5,376 KB
testcase_46	AC	54 ms; 5,376 KB
testcase_47	AC	60 ms; 5,376 KB

ソースコード

#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";
		}
	}
}