結果

問題 No.2292 Interval Union Find
ユーザー Ecrade_Ecrade_
提出日時 2023-05-05 22:19:30
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,346 bytes
コンパイル時間 1,725 ms
コンパイル使用メモリ 175,764 KB
実行使用メモリ 28,544 KB
最終ジャッジ日時 2024-11-23 08:44:10
合計ジャッジ時間 14,790 ms
ジャッジサーバーID
（参考情報） 		judge4 / 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 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 544 ms
28,416 KB
testcase_19 AC 446 ms
28,288 KB
testcase_20 AC 481 ms
28,544 KB
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 AC 22 ms
5,248 KB
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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) 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;
	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;
}
0