結果

問題 No.2292 Interval Union Find
ユーザー kotatsugamekotatsugame
提出日時 2023-05-05 21:43:58
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 193 ms / 5,000 ms
コード長 1,638 bytes
コンパイル時間 812 ms
コンパイル使用メモリ 77,452 KB
実行使用メモリ 12,724 KB
最終ジャッジ日時 2023-08-15 03:28:54
合計ジャッジ時間 10,287 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 60 ms
4,380 KB
testcase_05 AC 84 ms
4,380 KB
testcase_06 AC 59 ms
4,376 KB
testcase_07 AC 82 ms
4,376 KB
testcase_08 AC 87 ms
4,380 KB
testcase_09 AC 87 ms
4,380 KB
testcase_10 AC 79 ms
4,380 KB
testcase_11 AC 76 ms
4,380 KB
testcase_12 AC 88 ms
4,376 KB
testcase_13 AC 70 ms
4,380 KB
testcase_14 AC 72 ms
4,380 KB
testcase_15 AC 76 ms
4,376 KB
testcase_16 AC 73 ms
4,376 KB
testcase_17 AC 85 ms
4,380 KB
testcase_18 AC 122 ms
12,716 KB
testcase_19 AC 193 ms
12,716 KB
testcase_20 AC 192 ms
12,724 KB
testcase_21 AC 161 ms
8,864 KB
testcase_22 AC 169 ms
8,884 KB
testcase_23 AC 162 ms
8,948 KB
testcase_24 AC 152 ms
9,016 KB
testcase_25 AC 161 ms
8,876 KB
testcase_26 AC 168 ms
8,840 KB
testcase_27 AC 168 ms
8,848 KB
testcase_28 AC 165 ms
8,804 KB
testcase_29 AC 154 ms
9,040 KB
testcase_30 AC 157 ms
8,808 KB
testcase_31 AC 177 ms
8,812 KB
testcase_32 AC 178 ms
8,800 KB
testcase_33 AC 170 ms
8,896 KB
testcase_34 AC 167 ms
8,924 KB
testcase_35 AC 174 ms
9,012 KB
testcase_36 AC 174 ms
8,848 KB
testcase_37 AC 178 ms
8,860 KB
testcase_38 AC 178 ms
8,836 KB
testcase_39 AC 173 ms
8,840 KB
testcase_40 AC 175 ms
9,040 KB
testcase_41 AC 43 ms
4,380 KB
testcase_42 AC 44 ms
4,380 KB
testcase_43 AC 47 ms
4,376 KB
testcase_44 AC 54 ms
4,380 KB
testcase_45 AC 55 ms
4,380 KB
testcase_46 AC 57 ms
4,376 KB
testcase_47 AC 66 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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