#1186295 (C++23) No.3709 Unknown Treasure

• 問題: No.3709 Unknown Treasure
• ユーザー: あいすあうと
• 提出日時: 2026-09-11 22:29:40
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 76 ms / 2,000 ms
• コード長: 11,383 bytes
• コンパイル時間: 5,579 ms
• コンパイル使用メモリ: 415,172 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-09-11 22:30:09
• 合計ジャッジ時間: 9,357 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 36

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using i128=__int128;
using P=pair<ll,ll>;
template<typename T> using vc=vector<T>;
template<typename T> using vv=vc<vc<T>>;
using vl=vc<ll>;
using vvl=vc<vc<ll>>;
using vul=vc<ull>;
using vs=vc<string>;
using vb=vc<bool>;
#define rep(i,s,n) for(ll i=s;i<(n);i++)
#define Rep(i,s,n) for(ll i=n;i>=s;i--)
#define nall(x) x.begin(),x.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define nexp(v) next_permutation(v)
#define prep(v) prev_permutation(v)
#define YES cout<<"Yes"<<endl
#define NO cout<<"No"<<endl
#define YN {cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define M1 cout<<"-1"<<endl
const long long INF=(1LL<<62)-(1LL<<31)-1;
#define endl '\n'
using mint=modint998244353;
using mint7=modint1000000007;
//vl dx={1,-1,0,0};vl dy={0,0,1,-1};
//vl dx={0,0,1,1,1,-1,-1,-1};vl dy={1,-1,0,1,-1,0,1,-1};
bool out_grid(ll i, ll j, ll h, ll w){return (!(0<=i && i<h && 0<=j && j<w));}
void chmin(ll &a,ll b){if(a>b)a=b;}
void chmax(ll &a,ll b){if(a<b)a=b;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll ceil_div(ll a,ll b){return (a+(b-1))/b;}

template<typename T>
struct RangeSet{
	set<pair<T,T>> st;
	T TINF;

	RangeSet(){
		TINF=numeric_limits<T>::max()/2;
		st.emplace(TINF,TINF);
		st.emplace(-TINF,-TINF);
	}

	bool covered(T l,T r)const{
		assert(l<=r);
		auto ite=prev(st.lower_bound({l+1,l+1}));
		return ite->first<=l && r<=ite->second;
	}

	bool covered(T x)const{
		return covered(x,x);
	}

	pair<T,T> covered_by(T l,T r)const{
		assert(l<=r);
		auto ite=prev(st.lower_bound({l+1,l+1}));
		if(ite->first<=l && r<=ite->second)return *ite;
		return make_pair(-TINF,-TINF);
	}

	pair<T,T> covered_by(T x)const{
		return covered_by(x,x);
	}

	T insert(T l,T r){
		assert(l<=r);
		auto ite=prev(st.lower_bound({l+1,l+1}));
		if(ite->first<=l && r<=ite->second)return T(0);
		T sum_erased=T(0);
		if(ite->first<=l && l<=ite->second+1){
			l=ite->first;
			sum_erased+=ite->second-ite->first+1;
			ite=st.erase(ite);
		}else ite=next(ite);
		while(r>ite->second){
			sum_erased+=ite->second-ite->first+1;
			ite=st.erase(ite);
		}
		if(ite->first-1<=r && r<=ite->second){
			sum_erased+=ite->second-ite->first+1;
			r=ite->second;
			st.erase(ite);
		}
		st.emplace(l,r);
		return r-l+1-sum_erased;
	}

	T insert(T x){
		return insert(x,x);
	}

	T erase(T l,T r){
		assert(l<=r);
		auto ite=prev(st.lower_bound({l+1,l+1}));
		if(ite->first<=l && r<=ite->second){
			if(ite->first<l)st.emplace(ite->first,l-1);
			if(r<ite->second)st.emplace(r+1,ite->second);
			st.erase(ite);
			return r-l+1;
		}

		T ret=T(0);
		if(ite->first<=l && l<=ite->second){
			ret+=ite->second-l+1;
			if(ite->first<l)st.emplace(ite->first,l-1);
			ite=st.erase(ite);
		}else ite=next(ite);
		while(ite->second<=r){
			ret+=ite->second-ite->first+1;
			ite=st.erase(ite);
		}
		if(ite->first<=r && r<=ite->second){
			ret+=r-ite->first+1;
			if(r<ite->second)st.emplace(r+1,ite->second);
			st.erase(ite);
		}
		return ret;
	}

	T erase(T x){
		return erase(x,x);
	}

	int size()const{
		return (int)st.size()-2;
	}

	T mex(T x=0)const{
		auto ite=prev(st.lower_bound({x+1,x+1}));
		if(ite->first<=x && x<=ite->second)return ite->second+1;
		return x;
	}

	void output()const{
		cout<<"RangeSet : ";
		for(auto &p:st){
			if(p.first==-TINF || p.second==TINF)continue;
			cout<<"["<<p.first<<", "<<p.second<<"] ";
		}
		cout<<endl;
	}
};

template<typename T>
struct RangeSet2D{
	map<T,RangeSet<T>> mp;
	T TINF;

	RangeSet2D(){
		TINF=numeric_limits<T>::max()/2;
		mp.emplace(-TINF,RangeSet<T>());
		mp.emplace(TINF,RangeSet<T>());
	}

	typename map<T,RangeSet<T>>::iterator split(T x){
		auto ite=mp.lower_bound(x);
		if(ite!=mp.end() && ite->first==x)return ite;
		assert(ite!=mp.begin());
		return mp.emplace_hint(ite,x,prev(ite)->second);
	}

	void merge(T l,T r){
		auto ite=mp.lower_bound(l);
		if(ite!=mp.begin())ite=prev(ite);
		while(ite!=mp.end()){
			auto nxt=next(ite);
			if(nxt==mp.end() || nxt->first>r)break;
			if(nxt->first!=TINF && ite->second.st==nxt->second.st)mp.erase(nxt);
			else ite=nxt;
		}
	}

	bool covered(T xl,T xr,T yl,T yr)const{
		assert(xl<=xr && yl<=yr);
		assert(-TINF<xl && xr<TINF);
		auto ite=prev(mp.upper_bound(xl));
		while(true){
			if(!ite->second.covered(yl,yr))return false;
			auto nxt=next(ite);
			if(nxt==mp.end() || nxt->first>xr)break;
			ite=nxt;
		}
		return true;
	}

	bool covered(T x,T y)const{
		return covered(x,x,y,y);
	}

	T insert(T xl,T xr,T yl,T yr){
		assert(xl<=xr && yl<=yr);
		assert(-TINF<xl && xr<TINF-1);
		auto itr=split(xr+1);
		auto itl=split(xl);
		T ret=T(0);
		for(auto ite=itl;ite!=itr;++ite){
			auto nxt=next(ite);
			ret+=(nxt->first-ite->first)*ite->second.insert(yl,yr);
		}
		merge(xl,xr+1);
		return ret;
	}

	T insert(T x,T y){
		return insert(x,x,y,y);
	}

	T erase(T xl,T xr,T yl,T yr){
		assert(xl<=xr && yl<=yr);
		assert(-TINF<xl && xr<TINF-1);
		auto itr=split(xr+1);
		auto itl=split(xl);
		T ret=T(0);
		for(auto ite=itl;ite!=itr;++ite){
			auto nxt=next(ite);
			ret+=(nxt->first-ite->first)*ite->second.erase(yl,yr);
		}
		merge(xl,xr+1);
		return ret;
	}

	T erase(T x,T y){
		return erase(x,x,y,y);
	}

	T mex_y(T x,T y=0)const{
		assert(-TINF<x && x<TINF);
		auto ite=prev(mp.upper_bound(x));
		return ite->second.mex(y);
	}

	T mex_x(T y,T x=0)const{
		assert(-TINF<x && x<TINF);
		auto ite=prev(mp.upper_bound(x));
		while(ite->second.covered(y)){
			auto nxt=next(ite);
			x=nxt->first;
			ite=nxt;
		}
		return x;
	}

	ll size()const{
		ll ret=0;
		for(auto ite=mp.begin();next(ite)!=mp.end();++ite){
			ret+=ite->second.size();
		}
		return ret;
	}

	vc<array<T,4>> rectangles()const{
		vc<T> xs,ys;
		for(auto ite=mp.begin();next(ite)!=mp.end();++ite){
			auto nxt=next(ite);
			if(ite->first==-TINF || nxt->first==TINF)continue;
			bool ok=false;
			for(auto &p:ite->second.st){
				if(p.first==-ite->second.TINF || p.second==ite->second.TINF)continue;
				ok=true;
				ys.pb(p.first);
				ys.pb(p.second+1);
			}
			if(!ok)continue;
			xs.pb(ite->first);
			xs.pb(nxt->first);
		}
		if(xs.empty())return {};
		sort(nall(xs));
		xs.erase(unique(nall(xs)),xs.end());
		sort(nall(ys));
		ys.erase(unique(nall(ys)),ys.end());

		int nx=(int)xs.size()-1;
		int ny=(int)ys.size()-1;
		vc<vc<char>> a(nx,vc<char>(ny));

		rep(i,0,nx){
			auto ite=prev(mp.upper_bound(xs[i]));
			rep(j,0,ny){
				a[i][j]=ite->second.covered(ys[j]);
			}
		}

		struct R{
			int x,y,miss;
		};

		vc<R> rv;
		vc<vc<int>> id(nx+1,vc<int>(ny+1,-1));

		auto cell=[&](int x,int y)->int{
			if(x<0 || nx<=x || y<0 || ny<=y)return 0;
			return a[x][y];
		};

		rep(i,0,nx+1)rep(j,0,ny+1){
			array<int,4> q={
				cell(i-1,j-1),
				cell(i,j-1),
				cell(i-1,j),
				cell(i,j)
			};
			int cnt=q[0]+q[1]+q[2]+q[3];
			if(cnt!=3)continue;
			int miss=0;
			while(q[miss])miss++;
			id[i][j]=(int)rv.size();
			rv.pb({(int)i,(int)j,miss});
		}

		set<array<int,4>> hs,vs;

		for(auto [x,y,miss]:rv){
			if(miss==0 || miss==2){
				int k=x;
				while(k<nx && 0<y && y<ny && a[k][y-1] && a[k][y])k++;
				if(id[k][y]!=-1)hs.insert({x,y,k,y});
			}else{
				int k=x;
				while(0<k && 0<y && y<ny && a[k-1][y-1] && a[k-1][y])k--;
				if(id[k][y]!=-1)hs.insert({k,y,x,y});
			}

			if(miss==0 || miss==1){
				int k=y;
				while(k<ny && 0<x && x<nx && a[x-1][k] && a[x][k])k++;
				if(id[x][k]!=-1)vs.insert({x,y,x,k});
			}else{
				int k=y;
				while(0<k && 0<x && x<nx && a[x-1][k-1] && a[x][k-1])k--;
				if(id[x][k]!=-1)vs.insert({x,k,x,y});
			}
		}

		vc<array<int,4>> h(nall(hs));
		vc<array<int,4>> v(nall(vs));

		int H=(int)h.size();
		int V=(int)v.size();

		vc<vc<int>> g(H);

		rep(i,0,H)rep(j,0,V){
			if(h[i][0]<=v[j][0] && v[j][0]<=h[i][2] &&
			   v[j][1]<=h[i][1] && h[i][1]<=v[j][3]){
				g[i].pb(j);
			}
		}

		vc<int> mt(V,-1);
		vc<int> ml(H,-1);

		function<bool(int,vc<char>&)> dfs=[&](int x,vc<char> &seen)->bool{
			for(auto y:g[x]){
				if(seen[y])continue;
				seen[y]=1;
				if(mt[y]==-1 || dfs(mt[y],seen)){
					mt[y]=x;
					ml[x]=y;
					return true;
				}
			}
			return false;
		};

		rep(i,0,H){
			vc<char> seen(V);
			dfs(i,seen);
		}

		vc<char> zh(H);
		vc<char> zv(V);
		queue<pair<int,int>> q;

		rep(i,0,H){
			if(ml[i]!=-1)continue;
			zh[i]=1;
			q.emplace(0,i);
		}

		while(!q.empty()){
			auto [side,u]=q.front();
			q.pop();

			if(side==0){
				for(auto y:g[u]){
					if(ml[u]==y || zv[y])continue;
					zv[y]=1;
					q.emplace(1,y);
				}
			}else{
				if(mt[u]!=-1 && !zh[mt[u]]){
					zh[mt[u]]=1;
					q.emplace(0,mt[u]);
				}
			}
		}

		vc<vc<char>> hb(nx,vc<char>(ny+1));
		vc<vc<char>> vb(nx+1,vc<char>(ny));
		vc<vc<char>> used(nx+1,vc<char>(ny+1));

		rep(i,0,H){
			if(!zh[i])continue;
			auto [x1,y1,x2,y2]=h[i];
			rep(x,x1,x2)hb[x][y1]=1;
			used[x1][y1]=1;
			used[x2][y2]=1;
		}

		rep(i,0,V){
			if(zv[i])continue;
			auto [x1,y1,x2,y2]=v[i];
			rep(y,y1,y2)vb[x1][y]=1;
			used[x1][y1]=1;
			used[x2][y2]=1;
		}

		auto has_v=[&](int x,int y)->bool{
			return (y<ny && vb[x][y]) || (0<y && vb[x][y-1]);
		};

		for(auto [x,y,miss]:rv){
			if(used[x][y])continue;

			if(miss==0 || miss==2){
				int cur=x;
				while(cur<nx){
					if(has_v(cur,y))break;
					if(!(0<y && y<ny && a[cur][y-1] && a[cur][y]))break;
					hb[cur][y]=1;
					cur++;
				}
			}else{
				int cur=x;
				while(0<cur){
					if(has_v(cur,y))break;
					int k=cur-1;
					if(!(0<y && y<ny && a[k][y-1] && a[k][y]))break;
					hb[k][y]=1;
					cur--;
				}
			}
		}

		vc<vc<char>> seen(nx,vc<char>(ny));
		vc<array<T,4>> ret;

		rep(si,0,nx)rep(sj,0,ny){
			if(!a[si][sj] || seen[si][sj])continue;

			queue<pair<int,int>> que;
			que.emplace(si,sj);
			seen[si][sj]=1;

			int lx=si;
			int rx=si;
			int ly=sj;
			int ry=sj;
			ll cnt=0;

			while(!que.empty()){
				auto [x,y]=que.front();
				que.pop();

				cnt++;
				lx=min(lx,x);
				rx=max(rx,x);
				ly=min(ly,y);
				ry=max(ry,y);

				if(0<x && a[x-1][y] && !vb[x][y] && !seen[x-1][y]){
					seen[x-1][y]=1;
					que.emplace(x-1,y);
				}

				if(x+1<nx && a[x+1][y] && !vb[x+1][y] && !seen[x+1][y]){
					seen[x+1][y]=1;
					que.emplace(x+1,y);
				}

				if(0<y && a[x][y-1] && !hb[x][y] && !seen[x][y-1]){
					seen[x][y-1]=1;
					que.emplace(x,y-1);
				}

				if(y+1<ny && a[x][y+1] && !hb[x][y+1] && !seen[x][y+1]){
					seen[x][y+1]=1;
					que.emplace(x,y+1);
				}
			}

			assert(cnt==(ll)(rx-lx+1)*(ry-ly+1));

			ret.pb({
				xs[lx],
				ys[ly],
				xs[rx+1]-1,
				ys[ry+1]-1
			});
		}

		return ret;
	}

	void output()const{
		cout<<"RangeSet2D : ";
		for(auto ite=mp.begin();next(ite)!=mp.end();++ite){
			auto nxt=next(ite);
			for(auto &p:ite->second.st){
				if(p.first==-ite->second.TINF || p.second==ite->second.TINF)continue;
				if(ite->first==-TINF || nxt->first==TINF)continue;
				cout<<"["<<ite->first<<", "<<nxt->first-1<<"]x["<<p.first<<", "<<p.second<<"] ";
			}
		}
		cout<<endl;
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	ll h,w,n;
	cin >> h >> w >> n;
	RangeSet2D<ll> st;
	rep(i,0,n){
		ll r1,c1,r2,c2;
		cin >> r1 >> c1 >> r2 >> c2;
		st.insert(r1,r2,c1,c2);
	}
	auto rect=st.rectangles();
	//st.output();
	ll sum=0;
	for(auto [r1,c1,r2,c2]:rect)sum+=(r2-r1+1)*(c2-c1+1);
	cout << h*w-sum << endl;
}