#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
• 実行時間: 541 ms / 5,000 ms
• コード長: 2,388 bytes
• コンパイル時間: 1,709 ms
• コンパイル使用メモリ: 176,900 KB
• 実行使用メモリ: 28,544 KB
• 最終ジャッジ日時: 2024-11-23 09:03:20
• 合計ジャッジ時間: 14,413 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
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	62 ms; 5,248 KB
testcase_05	AC	154 ms; 5,248 KB
testcase_06	AC	59 ms; 5,248 KB
testcase_07	AC	149 ms; 5,248 KB
testcase_08	AC	135 ms; 5,248 KB
testcase_09	AC	133 ms; 5,248 KB
testcase_10	AC	104 ms; 5,248 KB
testcase_11	AC	94 ms; 5,248 KB
testcase_12	AC	143 ms; 5,248 KB
testcase_13	AC	69 ms; 5,248 KB
testcase_14	AC	79 ms; 5,248 KB
testcase_15	AC	89 ms; 5,248 KB
testcase_16	AC	77 ms; 5,248 KB
testcase_17	AC	114 ms; 5,248 KB
testcase_18	AC	541 ms; 28,416 KB
testcase_19	AC	416 ms; 28,544 KB
testcase_20	AC	440 ms; 28,544 KB
testcase_21	AC	320 ms; 18,304 KB
testcase_22	AC	325 ms; 18,304 KB
testcase_23	AC	324 ms; 18,304 KB
testcase_24	AC	320 ms; 18,304 KB
testcase_25	AC	309 ms; 18,304 KB
testcase_26	AC	326 ms; 18,304 KB
testcase_27	AC	320 ms; 18,304 KB
testcase_28	AC	319 ms; 18,304 KB
testcase_29	AC	312 ms; 18,304 KB
testcase_30	AC	320 ms; 18,304 KB
testcase_31	AC	312 ms; 18,304 KB
testcase_32	AC	311 ms; 18,304 KB
testcase_33	AC	309 ms; 18,304 KB
testcase_34	AC	305 ms; 18,304 KB
testcase_35	AC	323 ms; 18,304 KB
testcase_36	AC	325 ms; 18,432 KB
testcase_37	AC	309 ms; 18,176 KB
testcase_38	AC	314 ms; 18,304 KB
testcase_39	AC	313 ms; 18,304 KB
testcase_40	AC	316 ms; 18,304 KB
testcase_41	AC	21 ms; 5,248 KB
testcase_42	AC	30 ms; 5,248 KB
testcase_43	AC	43 ms; 5,248 KB
testcase_44	AC	58 ms; 5,248 KB
testcase_45	AC	59 ms; 5,248 KB
testcase_46	AC	69 ms; 5,248 KB
testcase_47	AC	82 ms; 5,248 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;
}