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

• 問題: No.2292 Interval Union Find
• ユーザー: Ecrade_
• 提出日時: 2023-05-05 22:24:44
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 573 ms / 5,000 ms
• コード長: 2,388 bytes
• コンパイル時間: 2,340 ms
• コンパイル使用メモリ: 173,428 KB
• 実行使用メモリ: 28,644 KB
• 最終ジャッジ日時: 2023-08-15 04:53:52
• 合計ジャッジ時間: 17,564 ms
• ジャッジサーバーID （参考情報）: judge13 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,384 KB
testcase_01	AC	2 ms; 4,380 KB
testcase_02	AC	2 ms; 4,380 KB
testcase_03	AC	2 ms; 4,384 KB
testcase_04	AC	62 ms; 4,380 KB
testcase_05	AC	156 ms; 4,384 KB
testcase_06	AC	59 ms; 4,380 KB
testcase_07	AC	150 ms; 4,388 KB
testcase_08	AC	136 ms; 4,380 KB
testcase_09	AC	135 ms; 4,380 KB
testcase_10	AC	105 ms; 4,384 KB
testcase_11	AC	95 ms; 4,384 KB
testcase_12	AC	143 ms; 4,384 KB
testcase_13	AC	70 ms; 4,384 KB
testcase_14	AC	83 ms; 4,380 KB
testcase_15	AC	90 ms; 4,380 KB
testcase_16	AC	78 ms; 4,380 KB
testcase_17	AC	115 ms; 4,384 KB
testcase_18	AC	544 ms; 28,324 KB
testcase_19	AC	509 ms; 28,332 KB
testcase_20	AC	573 ms; 28,644 KB
testcase_21	AC	392 ms; 18,140 KB
testcase_22	AC	393 ms; 18,176 KB
testcase_23	AC	396 ms; 18,108 KB
testcase_24	AC	392 ms; 18,308 KB
testcase_25	AC	391 ms; 18,136 KB
testcase_26	AC	392 ms; 18,140 KB
testcase_27	AC	400 ms; 18,116 KB
testcase_28	AC	393 ms; 18,140 KB
testcase_29	AC	391 ms; 18,168 KB
testcase_30	AC	394 ms; 18,368 KB
testcase_31	AC	391 ms; 18,176 KB
testcase_32	AC	393 ms; 18,268 KB
testcase_33	AC	401 ms; 18,160 KB
testcase_34	AC	391 ms; 18,156 KB
testcase_35	AC	396 ms; 18,176 KB
testcase_36	AC	390 ms; 18,132 KB
testcase_37	AC	390 ms; 18,160 KB
testcase_38	AC	394 ms; 18,396 KB
testcase_39	AC	389 ms; 18,276 KB
testcase_40	AC	396 ms; 18,144 KB
testcase_41	AC	20 ms; 4,384 KB
testcase_42	AC	29 ms; 4,388 KB
testcase_43	AC	42 ms; 4,380 KB
testcase_44	AC	59 ms; 4,380 KB
testcase_45	AC	58 ms; 4,380 KB
testcase_46	AC	69 ms; 4,384 KB
testcase_47	AC	83 ms; 4,380 KB

ソースコード

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,o,l,r,x,y,a[200009];
pair <ll,ll> tmp[200009];
struct st{ll l,r; mutable ll v; bool operator < (const st &a) const{return l < a.l;}};
set <st> s;
inline ll read(){
	ll s = 0,w = 1;
	char ch = getchar();
	while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
	while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
	return s * w;
}
ll qp(ll x,ll y,ll mod){
	ll a = 1,b = x % mod;
	while (y){
		if (y & 1) a = a * b % mod;
		b = b * b % mod,y >>= 1;
	}
	return a;
}
set <st> :: iterator split(ll pos){
	set <st> :: iterator it = s.lower_bound((st){pos,pos,0});
	if (it != s.end() && it -> l == pos) return it;
	it --;
	if (it -> r < pos) return s.end();
	st now = *it;
	s.erase(it),s.insert((st){now.l,pos - 1,now.v});
	return s.insert((st){pos,now.r,now.v}).first;
}
void assign(ll l,ll r,ll v){
	set <st> :: iterator itr = split(r + 1),itl = split(l);
	s.erase(itl,itr),s.insert((st){l,r,v});
	set <st> :: iterator it = s.lower_bound((st){l,l,0});
	set <st> :: iterator it2 = s.upper_bound((st){l,l,0});
	if (it2 != s.end()){
		if (it2 -> v == it -> v){
			st qwq = (st){it -> l,it2 -> r,it -> v};
			s.erase(it),s.erase(it2);
			s.insert(qwq);
		}
	}
	it = s.lower_bound((st){l,l,0});
	if (it != s.begin()){
		set <st> :: iterator it2 = (-- s.lower_bound((st){l,l,0}));
		if (it2 -> v == it -> v){
			st qwq = (st){it2 -> l,it -> r,it -> v};
			s.erase(it),s.erase(it2);
			s.insert(qwq);
		}
	}
}
void query(ll x,ll y){
	if (x > y) swap(x,y);
	if (x == y){puts("1"); return;}
	if (!s.size()){puts("0"); return;}
	set <st> :: iterator it = -- s.upper_bound((st){x,x,0});
	if (it -> v == 0 || (it -> v == 1 && it -> r < y - 1)) puts("0");
	else puts("1");
}
void query2(ll x){
	if (!s.size()){puts("1"); return;}
	set <st> :: iterator it = -- s.upper_bound((st){x,x,0});
	ll ans = 1;
	if (it -> v == 1) ans += it -> r - it -> l + 1;
	else if (it != s.begin()){
		it --;
		if (it -> r == x - 1 && it -> v == 1) ans += it -> r - it -> l + 1;
	}
	printf("%lld\n",ans);
}
int main(){
	n = read(),m = read();
	s.insert((st){1,n - 1,0});
	while (m --){
		o = read();
		if (o == 1) l = read(),r = read(),assign(l,r - 1,1);
		if (o == 2) l = read(),r = read(),assign(l,r - 1,0);
		if (o == 3) x = read(),y = read(),query(x,y);
		if (o == 4) x = read(),query2(x);
	}
	return 0;
}