#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
• 実行時間: 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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	63 ms; 5,248 KB
testcase_05	AC	89 ms; 5,248 KB
testcase_06	AC	62 ms; 5,248 KB
testcase_07	AC	85 ms; 5,248 KB
testcase_08	AC	91 ms; 5,248 KB
testcase_09	AC	91 ms; 5,248 KB
testcase_10	AC	83 ms; 5,248 KB
testcase_11	AC	79 ms; 5,248 KB
testcase_12	AC	93 ms; 5,248 KB
testcase_13	AC	75 ms; 5,248 KB
testcase_14	AC	76 ms; 5,248 KB
testcase_15	AC	80 ms; 5,248 KB
testcase_16	AC	77 ms; 5,248 KB
testcase_17	AC	89 ms; 5,248 KB
testcase_18	AC	124 ms; 12,800 KB
testcase_19	AC	213 ms; 12,928 KB
testcase_20	AC	211 ms; 12,800 KB
testcase_21	AC	177 ms; 9,088 KB
testcase_22	AC	186 ms; 8,832 KB
testcase_23	AC	180 ms; 8,832 KB
testcase_24	AC	176 ms; 8,832 KB
testcase_25	AC	174 ms; 8,832 KB
testcase_26	AC	173 ms; 8,960 KB
testcase_27	AC	175 ms; 8,832 KB
testcase_28	AC	176 ms; 8,832 KB
testcase_29	AC	176 ms; 8,832 KB
testcase_30	AC	178 ms; 8,832 KB
testcase_31	AC	174 ms; 8,960 KB
testcase_32	AC	170 ms; 8,832 KB
testcase_33	AC	178 ms; 8,832 KB
testcase_34	AC	184 ms; 8,832 KB
testcase_35	AC	177 ms; 8,832 KB
testcase_36	AC	175 ms; 8,832 KB
testcase_37	AC	187 ms; 8,832 KB
testcase_38	AC	174 ms; 8,832 KB
testcase_39	AC	174 ms; 8,960 KB
testcase_40	AC	173 ms; 8,832 KB
testcase_41	AC	45 ms; 5,248 KB
testcase_42	AC	46 ms; 5,248 KB
testcase_43	AC	50 ms; 5,248 KB
testcase_44	AC	56 ms; 5,248 KB
testcase_45	AC	57 ms; 5,248 KB
testcase_46	AC	59 ms; 5,248 KB
testcase_47	AC	67 ms; 5,248 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";
		}
	}
}