#1186431 (C++23(gcc16)) No.3709 Unknown Treasure

• 問題: No.3709 Unknown Treasure
• ユーザー: あいすあうと
• 提出日時: 2026-09-12 00:13:59
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: RE
• 実行時間: -
• コード長: 23,513 bytes
• コンパイル時間: 9,311 ms
• コンパイル使用メモリ: 516,644 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-09-12 00:14:17
• 合計ジャッジ時間: 15,334 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 1 RE * 2
other	AC * 2 WA * 1 RE * 33

ソースコード

#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{
	struct Node;
	using NP=shared_ptr<const Node>;
	using IV=vc<pair<T,T>>;
	struct Node{
		T l,r,sum;
		ull pri,h1,h2;
		int cnt;
		NP lc,rc;
		Node(T l,T r,ull pri,NP lc,NP rc,T sum,int cnt,ull h1,ull h2):l(l),r(r),sum(sum),pri(pri),h1(h1),h2(h2),cnt(cnt),lc(lc),rc(rc){}
	};
	struct HSeg{T x1,y,x2;};
	struct VSeg{T x,y1,y2;};
	struct Reflex{T x,y;int miss;};

	static ull mix(ull x){
		x+=0x9e3779b97f4a7c15ULL;
		x=(x^(x>>30))*0xbf58476d1ce4e5b9ULL;
		x=(x^(x>>27))*0x94d049bb133111ebULL;
		return x^(x>>31);
	}
	struct PairHash{
		size_t operator()(const pair<T,T> &p)const{
			ull a=(ull)hash<T>{}(p.first),b=(ull)hash<T>{}(p.second);
			return (size_t)mix(a^mix(b+0x9e3779b97f4a7c15ULL));
		}
	};

	map<T,NP> mp;
	T TINF;

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

	static T ysum(const NP &p){return p?p->sum:T(0);}
	static int ycnt(const NP &p){return p?p->cnt:0;}
	static ull yh1(const NP &p){return p?p->h1:0x243f6a8885a308d3ULL;}
	static ull yh2(const NP &p){return p?p->h2:0x13198a2e03707344ULL;}

	static ull priority(T x){
		return mix((ull)hash<T>{}(x)+0x9e3779b97f4a7c15ULL);
	}

	static bool higher(const NP &a,const NP &b){
		if(a->pri!=b->pri)return a->pri>b->pri;
		return a->l>b->l;
	}

	static NP make_node(T l,T r,const NP &lc=NP(),const NP &rc=NP()){
		ull p=priority(l);
		T s=ysum(lc)+(r-l+1)+ysum(rc);
		int c=ycnt(lc)+1+ycnt(rc);
		ull z1=mix((ull)hash<T>{}(l)^mix((ull)hash<T>{}(r)+0x243f6a8885a308d3ULL));
		ull z2=mix((ull)hash<T>{}(l)+0x13198a2e03707344ULL)^mix((ull)hash<T>{}(r));
		ull h1=mix(yh1(lc)^z1^mix(yh1(rc)+0xa4093822299f31d0ULL));
		ull h2=mix(yh2(lc)+z2+mix(yh2(rc)^0x082efa98ec4e6c89ULL));
		return make_shared<Node>(l,r,p,lc,rc,s,c,h1,h2);
	}

	static pair<NP,NP> ysplit(const NP &p,T key){
		if(!p)return {};
		if(p->l<key){
			auto [a,b]=ysplit(p->rc,key);
			return {make_node(p->l,p->r,p->lc,a),b};
		}else{
			auto [a,b]=ysplit(p->lc,key);
			return {a,make_node(p->l,p->r,b,p->rc)};
		}
	}

	static NP ymerge(const NP &a,const NP &b){
		if(!a)return b;
		if(!b)return a;
		if(higher(a,b))return make_node(a->l,a->r,a->lc,ymerge(a->rc,b));
		return make_node(b->l,b->r,ymerge(a,b->lc),b->rc);
	}

	static const Node* yprev(const NP &p,T x){
		const Node *ans=nullptr;
		auto cur=p;
		while(cur){
			if(cur->l<=x){ans=cur.get();cur=cur->rc;}
			else cur=cur->lc;
		}
		return ans;
	}

	static const Node* ylower(const NP &p,T x){
		const Node *ans=nullptr;
		auto cur=p;
		while(cur){
			if(cur->l>=x){ans=cur.get();cur=cur->lc;}
			else cur=cur->rc;
		}
		return ans;
	}

	static const Node* yfirst(const NP &p){
		if(!p)return nullptr;
		auto cur=p;
		while(cur->lc)cur=cur->lc;
		return cur.get();
	}

	static const Node* ylast(const NP &p){
		if(!p)return nullptr;
		auto cur=p;
		while(cur->rc)cur=cur->rc;
		return cur.get();
	}

	static bool yequal_exact(const NP &a,const NP &b){
		if(a.get()==b.get())return true;
		if(!a || !b)return false;
		if(a->l!=b->l || a->r!=b->r)return false;
		return yequal_exact(a->lc,b->lc) && yequal_exact(a->rc,b->rc);
	}

	static bool yequal(const NP &a,const NP &b){
		if(a.get()==b.get())return true;
		if(!a || !b)return false;
		if(a->cnt!=b->cnt || a->sum!=b->sum || a->h1!=b->h1 || a->h2!=b->h2)return false;
		return yequal_exact(a,b);
	}

	static bool ycovered(const NP &p,T l,T r){
		assert(l<=r);
		auto z=yprev(p,l);
		return z && z->l<=l && r<=z->r;
	}

	static T ymex(const NP &p,T x){
		auto z=yprev(p,x);
		if(z && z->l<=x && x<=z->r)return z->r+1;
		return x;
	}

	static pair<NP,T> yinsert(const NP &root,T l,T r){
		assert(l<=r);
		auto pre=yprev(root,l);
		if(pre && pre->l<=l && r<=pre->r)return {root,T(0)};
		T cut=l;
		if(pre && pre->r+1>=l)cut=pre->l;
		auto [a,b]=ysplit(root,cut);
		auto [m,c]=ysplit(b,r+2);
		T nl=l,nr=r;
		if(m){
			nl=min(nl,yfirst(m)->l);
			nr=max(nr,ylast(m)->r);
		}
		T d=nr-nl+1-ysum(m);
		auto z=make_node(nl,nr);
		return {ymerge(a,ymerge(z,c)),d};
	}

	static pair<NP,T> yerase(const NP &root,T l,T r){
		assert(l<=r);
		auto pre=yprev(root,l);
		bool hit=pre && pre->r>=l;
		if(!hit){
			auto nx=ylower(root,l);
			if(!nx || nx->l>r)return {root,T(0)};
		}
		T cut=hit?pre->l:l;
		auto [a,b]=ysplit(root,cut);
		auto [m,c]=ysplit(b,r+1);
		if(!m)return {root,T(0)};
		auto f=yfirst(m);
		auto z=ylast(m);
		NP mid;
		T keep=T(0);
		if(f->l<l){
			mid=ymerge(mid,make_node(f->l,l-1));
			keep+=l-f->l;
		}
		if(r<z->r){
			mid=ymerge(mid,make_node(r+1,z->r));
			keep+=z->r-r;
		}
		T d=ysum(m)-keep;
		return {ymerge(a,ymerge(mid,c)),d};
	}

	static void yintervals(const NP &root,IV &v){
		vc<NP> st;
		auto cur=root;
		while(cur || !st.empty()){
			while(cur){st.pb(cur);cur=cur->lc;}
			cur=st.back();st.pop_back();
			v.pb({cur->l,cur->r});
			cur=cur->rc;
		}
	}

	typename map<T,NP>::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 && yequal(ite->second,nxt->second))mp.erase(nxt);
			else ite=nxt;
		}
	}

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

	bool covered(T r,T c)const{return covered(r,c,r,c);}

	T insert(T r1,T c1,T r2,T c2){
		assert(r1<=r2 && c1<=c2);
		assert(-TINF<r1 && r2<TINF-1 && -TINF<c1 && c2<TINF-1);
		auto itr=split(r2+1);
		auto itl=split(r1);
		struct U{NP root;T d;};
		unordered_map<const Node*,U> memo;
		T ret=T(0);
		for(auto ite=itl;ite!=itr;++ite){
			const Node *key=ite->second.get();
			auto f=memo.find(key);
			if(f==memo.end()){
				auto [nr,d]=yinsert(ite->second,c1,c2);
				f=memo.emplace(key,U{nr,d}).first;
			}
			auto nxt=next(ite);
			ret+=(nxt->first-ite->first)*f->second.d;
			ite->second=f->second.root;
		}
		merge(r1,r2+1);
		return ret;
	}

	T insert(T r,T c){return insert(r,c,r,c);}

	T erase(T r1,T c1,T r2,T c2){
		assert(r1<=r2 && c1<=c2);
		assert(-TINF<r1 && r2<TINF-1 && -TINF<c1 && c2<TINF-1);
		auto itr=split(r2+1);
		auto itl=split(r1);
		struct U{NP root;T d;};
		unordered_map<const Node*,U> memo;
		T ret=T(0);
		for(auto ite=itl;ite!=itr;++ite){
			const Node *key=ite->second.get();
			auto f=memo.find(key);
			if(f==memo.end()){
				auto [nr,d]=yerase(ite->second,c1,c2);
				f=memo.emplace(key,U{nr,d}).first;
			}
			auto nxt=next(ite);
			ret+=(nxt->first-ite->first)*f->second.d;
			ite->second=f->second.root;
		}
		merge(r1,r2+1);
		return ret;
	}

	T erase(T r,T c){return erase(r,c,r,c);}

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

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

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

	static bool iv_covered(const IV &v,T l,T r){
		if(l>r)return true;
		int lo=0,hi=(int)v.size();
		while(lo<hi){
			int md=(lo+hi)/2;
			if(v[md].first<=l)lo=md+1;
			else hi=md;
		}
		if(lo==0)return false;
		auto [a,b]=v[lo-1];
		return a<=l && r<=b;
	}

	static shared_ptr<IV> intersect_iv(const shared_ptr<IV> &a,const shared_ptr<IV> &b,const shared_ptr<IV> &empty){
		if(a.get()==b.get())return a;
		if(a->empty() || b->empty())return empty;
		auto c=make_shared<IV>();
		int i=0,j=0;
		while(i<(int)a->size() && j<(int)b->size()){
			T l=max((*a)[i].first,(*b)[j].first);
			T r=min((*a)[i].second,(*b)[j].second);
			if(l<=r)c->pb({l,r});
			if((*a)[i].second<(*b)[j].second)i++;
			else j++;
		}
		if(c->empty())return empty;
		return c;
	}

	vc<array<T,4>> rectangles()const{
		vc<pair<T,NP>> nodes;
		for(auto ite=next(mp.begin());ite!=mp.end() && ite->first!=TINF;++ite)nodes.pb(*ite);
		if(nodes.size()<2)return {};

		unordered_map<const Node*,shared_ptr<IV>> cache;
		auto empty=make_shared<IV>();
		auto get_iv=[&](const NP &p)->shared_ptr<IV>{
			if(!p)return empty;
			auto f=cache.find(p.get());
			if(f!=cache.end())return f->second;
			auto v=make_shared<IV>();
			v->reserve(ycnt(p));
			yintervals(p,*v);
			cache[p.get()]=v;
			return v;
		};

		int nx=(int)nodes.size()-1;
		vc<T> xs(nodes.size());
		vc<shared_ptr<IV>> siv(nodes.size());
		rep(i,0,(ll)nodes.size()){
			xs[i]=nodes[i].first;
			siv[i]=get_iv(nodes[i].second);
		}

		vc<HSeg> hbound;
		vc<VSeg> vbound;
		vc<Reflex> rv;

		rep(i,0,nx){
			T x1=xs[i],x2=xs[i+1];
			for(auto [l,r]:*siv[i]){
				hbound.pb({x1,l,x2});
				hbound.pb({x1,r+1,x2});
			}
		}

		auto transition=[&](T x,const IV &a,const IV &b){
			vc<T> ea,eb;
			ea.reserve(a.size()*2);
			eb.reserve(b.size()*2);
			for(auto [l,r]:a){ea.pb(l);ea.pb(r+1);}
			for(auto [l,r]:b){eb.pb(l);eb.pb(r+1);}
			int i=0,j=0;
			bool sa=false,sb=false,has=false;
			T pre=T();
			while(i<(int)ea.size() || j<(int)eb.size()){
				T y;
				if(j==(int)eb.size() || (i<(int)ea.size() && ea[i]<eb[j]))y=ea[i];
				else if(i==(int)ea.size() || eb[j]<ea[i])y=eb[j];
				else y=ea[i];
				if(has && pre<y && sa!=sb)vbound.pb({x,pre,y});
				bool ba=sa,bb=sb;
				if(i<(int)ea.size() && ea[i]==y){sa=!sa;i++;}
				if(j<(int)eb.size() && eb[j]==y){sb=!sb;j++;}
				int q[4]={(int)ba,(int)bb,(int)sa,(int)sb};
				int cnt=q[0]+q[1]+q[2]+q[3];
				if(cnt==3){
					int miss=0;
					while(q[miss])miss++;
					rv.pb({x,y,miss});
				}
				pre=y;
				has=true;
			}
		};

		transition(xs[0],*empty,*siv[0]);
		rep(i,1,(ll)nodes.size())transition(xs[i],*siv[i-1],*siv[i]);

		int segN=1;
		while(segN<nx)segN<<=1;
		vc<shared_ptr<IV>> seg(segN*2,empty);
		rep(i,0,nx)seg[segN+i]=siv[i];
		for(int i=segN-1;i;i--)seg[i]=intersect_iv(seg[i<<1],seg[i<<1|1],empty);

		auto range_covered=[&](int l,int r,T a,T b)->bool{
			l+=segN;
			r+=segN;
			while(l<r){
				if(l&1){if(!iv_covered(*seg[l],a,b))return false;l++;}
				if(r&1){--r;if(!iv_covered(*seg[r],a,b))return false;}
				l>>=1;
				r>>=1;
			}
			return true;
		};

		int R=(int)rv.size();
		vc<int> ord(R);
		iota(nall(ord),0);
		vc<HSeg> hc;
		vc<VSeg> vcand;

		sort(nall(ord),[&](int a,int b){
			if(rv[a].y!=rv[b].y)return rv[a].y<rv[b].y;
			return rv[a].x<rv[b].x;
		});
		rep(k,1,R){
			auto &a=rv[ord[k-1]];
			auto &b=rv[ord[k]];
			if(a.y!=b.y || a.x==b.x)continue;
			int l=lower_bound(nall(xs),a.x)-xs.begin();
			int r=lower_bound(nall(xs),b.x)-xs.begin();
			if(range_covered(l,r,a.y-1,a.y))hc.pb({a.x,a.y,b.x});
		}

		sort(nall(ord),[&](int a,int b){
			if(rv[a].x!=rv[b].x)return rv[a].x<rv[b].x;
			return rv[a].y<rv[b].y;
		});
		rep(k,1,R){
			auto &a=rv[ord[k-1]];
			auto &b=rv[ord[k]];
			if(a.x!=b.x || a.y==b.y)continue;
			int z=lower_bound(nall(xs),a.x)-xs.begin();
			auto L=(z==0?empty:siv[z-1]);
			auto RR=siv[z];
			if(iv_covered(*L,a.y,b.y-1) && iv_covered(*RR,a.y,b.y-1))vcand.pb({a.x,a.y,b.y});
		}

		int H=(int)hc.size(),V=(int)vcand.size();
		vc<vc<int>> g(H);
		struct Ev{T x;int tp,id;};
		vc<Ev> ev;
		ev.reserve(H*2+V);
		rep(i,0,H){ev.pb({hc[i].x1,0,(int)i});ev.pb({hc[i].x2,2,(int)i});}
		rep(i,0,V)ev.pb({vcand[i].x,1,(int)i});
		sort(nall(ev),[](const Ev &a,const Ev &b){
			if(a.x!=b.x)return a.x<b.x;
			return a.tp<b.tp;
		});
		set<pair<T,int>> active;
		for(auto e:ev){
			if(e.tp==0)active.emplace(hc[e.id].y,e.id);
			else if(e.tp==2)active.erase({hc[e.id].y,e.id});
			else{
				auto &v=vcand[e.id];
				auto ite=active.lower_bound({v.y1,numeric_limits<int>::min()});
				while(ite!=active.end() && ite->first<=v.y2){
					g[ite->second].pb(e.id);
					++ite;
				}
			}
		}

		vc<int> ml(H,-1),mr(V,-1),dist(H);
		auto bfs=[&]()->bool{
			queue<int> q;
			fill(nall(dist),-1);
			rep(i,0,H)if(ml[i]==-1){dist[i]=0;q.push(i);}
			bool ok=false;
			while(!q.empty()){
				int u=q.front();q.pop();
				for(int v:g[u]){
					int w=mr[v];
					if(w==-1)ok=true;
					else if(dist[w]==-1){dist[w]=dist[u]+1;q.push(w);}
				}
			}
			return ok;
		};
		auto dfs=[&](auto &&self,int u)->bool{
			for(int v:g[u]){
				int w=mr[v];
				if(w==-1 || (dist[w]==dist[u]+1 && self(self,w))){
					ml[u]=v;
					mr[v]=u;
					return true;
				}
			}
			dist[u]=-1;
			return false;
		};
		while(bfs())rep(i,0,H)if(ml[i]==-1)dfs(dfs,i);

		vc<char> zh(H),zv(V);
		queue<pair<int,int>> q;
		rep(i,0,H)if(ml[i]==-1){zh[i]=1;q.emplace(0,i);}
		while(!q.empty()){
			auto [s,u]=q.front();q.pop();
			if(s==0){
				for(int v:g[u]){
					if(ml[u]==v || zv[v])continue;
					zv[v]=1;
					q.emplace(1,v);
				}
			}else if(mr[u]!=-1 && !zh[mr[u]]){
				zh[mr[u]]=1;
				q.emplace(0,mr[u]);
			}
		}

		vc<HSeg> selh;
		vc<VSeg> selv;
		unordered_set<pair<T,T>,PairHash> used;
		rep(i,0,H)if(zh[i]){
			selh.pb(hc[i]);
			used.emplace(hc[i].x1,hc[i].y);
			used.emplace(hc[i].x2,hc[i].y);
		}
		rep(i,0,V)if(!zv[i]){
			selv.pb(vcand[i]);
			used.emplace(vcand[i].x,vcand[i].y1);
			used.emplace(vcand[i].x,vcand[i].y2);
		}

		vc<int> rem;
		rep(i,0,R)if(!used.contains({rv[i].x,rv[i].y}))rem.pb(i);
		vc<HSeg> ext;
		vc<VSeg> barriers=vbound;
		for(auto z:selv)barriers.pb(z);

		if(!rem.empty()){
			vc<T> ys;
			ys.reserve(rem.size());
			for(int i:rem)ys.pb(rv[i].y);
			sort(nall(ys));
			ys.erase(unique(nall(ys)),ys.end());
			int sn=1;
			while(sn<(int)ys.size())sn<<=1;
			vc<T> mx(sn*2,-TINF),mn(sn*2,TINF);
			auto updmax=[&](int l,int r,T x){
				for(l+=sn,r+=sn;l<r;l>>=1,r>>=1){
					if(l&1)mx[l]=max(mx[l],x),l++;
					if(r&1)--r,mx[r]=max(mx[r],x);
				}
			};
			auto updmin=[&](int l,int r,T x){
				for(l+=sn,r+=sn;l<r;l>>=1,r>>=1){
					if(l&1)mn[l]=min(mn[l],x),l++;
					if(r&1)--r,mn[r]=min(mn[r],x);
				}
			};
			auto getmax=[&](int p){
				T ret=-TINF;
				for(p+=sn;p;p>>=1)ret=max(ret,mx[p]);
				return ret;
			};
			auto getmin=[&](int p){
				T ret=TINF;
				for(p+=sn;p;p>>=1)ret=min(ret,mn[p]);
				return ret;
			};
			vc<int> bo(barriers.size()),qo=rem;
			iota(nall(bo),0);
			sort(nall(bo),[&](int a,int b){return barriers[a].x<barriers[b].x;});
			sort(nall(qo),[&](int a,int b){return rv[a].x<rv[b].x;});
			vc<T> lans(R,-TINF),rans(R,TINF);
			int p=0;
			for(int id:qo){
				while(p<(int)bo.size() && barriers[bo[p]].x<rv[id].x){
					auto z=barriers[bo[p++]];
					int l=lower_bound(nall(ys),z.y1)-ys.begin();
					int r=upper_bound(nall(ys),z.y2)-ys.begin();
					if(l<r)updmax(l,r,z.x);
				}
				int y=lower_bound(nall(ys),rv[id].y)-ys.begin();
				lans[id]=getmax(y);
			}
			fill(nall(mn),TINF);
			sort(nall(bo),[&](int a,int b){return barriers[a].x>barriers[b].x;});
			sort(nall(qo),[&](int a,int b){return rv[a].x>rv[b].x;});
			p=0;
			for(int id:qo){
				while(p<(int)bo.size() && barriers[bo[p]].x>rv[id].x){
					auto z=barriers[bo[p++]];
					int l=lower_bound(nall(ys),z.y1)-ys.begin();
					int r=upper_bound(nall(ys),z.y2)-ys.begin();
					if(l<r)updmin(l,r,z.x);
				}
				int y=lower_bound(nall(ys),rv[id].y)-ys.begin();
				rans[id]=getmin(y);
			}
			for(int id:rem){
				auto z=rv[id];
				if(z.miss==0 || z.miss==2){
					assert(rans[id]!=TINF);
					ext.pb({z.x,z.y,rans[id]});
				}else{
					assert(lans[id]!=-TINF);
					ext.pb({lans[id],z.y,z.x});
				}
			}
		}

		vc<HSeg> hs=hbound;
		hs.insert(hs.end(),nall(selh));
		hs.insert(hs.end(),nall(ext));
		vc<VSeg> vs=vbound;
		vs.insert(vs.end(),nall(selv));

		auto merge_h=[&](vc<HSeg> a){
			sort(nall(a),[](const HSeg &p,const HSeg &q){
				if(p.y!=q.y)return p.y<q.y;
				if(p.x1!=q.x1)return p.x1<q.x1;
				return p.x2<q.x2;
			});
			vc<HSeg> b;
			for(auto z:a){
				if(z.x1==z.x2)continue;
				if(b.empty() || b.back().y!=z.y || b.back().x2<z.x1)b.pb(z);
				else b.back().x2=max(b.back().x2,z.x2);
			}
			return b;
		};
		auto merge_v=[&](vc<VSeg> a){
			sort(nall(a),[](const VSeg &p,const VSeg &q){
				if(p.x!=q.x)return p.x<q.x;
				if(p.y1!=q.y1)return p.y1<q.y1;
				return p.y2<q.y2;
			});
			vc<VSeg> b;
			for(auto z:a){
				if(z.y1==z.y2)continue;
				if(b.empty() || b.back().x!=z.x || b.back().y2<z.y1)b.pb(z);
				else b.back().y2=max(b.back().y2,z.y2);
			}
			return b;
		};
		hs=merge_h(move(hs));
		vs=merge_v(move(vs));

		vc<vc<T>> hp(hs.size()),vp(vs.size());
		rep(i,0,(ll)hs.size()){hp[i].pb(hs[i].x1);hp[i].pb(hs[i].x2);}
		rep(i,0,(ll)vs.size()){vp[i].pb(vs[i].y1);vp[i].pb(vs[i].y2);}
		vc<Ev> ev2;
		ev2.reserve(hs.size()*2+vs.size());
		rep(i,0,(ll)hs.size()){ev2.pb({hs[i].x1,0,(int)i});ev2.pb({hs[i].x2,2,(int)i});}
		rep(i,0,(ll)vs.size())ev2.pb({vs[i].x,1,(int)i});
		sort(nall(ev2),[](const Ev &a,const Ev &b){
			if(a.x!=b.x)return a.x<b.x;
			return a.tp<b.tp;
		});
		active.clear();
		for(auto e:ev2){
			if(e.tp==0)active.emplace(hs[e.id].y,e.id);
			else if(e.tp==2)active.erase({hs[e.id].y,e.id});
			else{
				auto z=vs[e.id];
				auto ite=active.lower_bound({z.y1,numeric_limits<int>::min()});
				while(ite!=active.end() && ite->first<=z.y2){
					hp[ite->second].pb(z.x);
					vp[e.id].pb(ite->first);
					++ite;
				}
			}
		}

		using Point=pair<T,T>;
		vc<pair<Point,Point>> edges;
		rep(i,0,(ll)hs.size()){
			auto &v=hp[i];
			sort(nall(v));
			v.erase(unique(nall(v)),v.end());
			rep(j,1,(ll)v.size())if(v[j-1]<v[j])edges.pb({{v[j-1],hs[i].y},{v[j],hs[i].y}});
		}
		rep(i,0,(ll)vs.size()){
			auto &v=vp[i];
			sort(nall(v));
			v.erase(unique(nall(v)),v.end());
			rep(j,1,(ll)v.size())if(v[j-1]<v[j])edges.pb({{vs[i].x,v[j-1]},{vs[i].x,v[j]}});
		}

		unordered_map<Point,int,PairHash> pid;
		vc<Point> pt;
		vc<array<int,4>> adj;
		auto gid=[&](Point p){
			auto f=pid.find(p);
			if(f!=pid.end())return f->second;
			int id=pt.size();
			pid[p]=id;
			pt.pb(p);
			adj.pb({-1,-1,-1,-1});
			return id;
		};
		auto dir=[&](Point a,Point b){
			if(b.first<a.first)return 0;
			if(b.second>a.second)return 1;
			if(b.first>a.first)return 2;
			return 3;
		};
		for(auto [a,b]:edges){
			int u=gid(a),v=gid(b);
			int d=dir(a,b);
			adj[u][d]=v;
			adj[v][(d+2)%4]=u;
		}

		vc<array<char,4>> seen(pt.size());
		vc<array<T,4>> ret;
		rep(s,0,(ll)pt.size())rep(sd,0,4){
			if(adj[s][sd]==-1 || seen[s][sd])continue;
			int u=s,d=sd;
			T lx=pt[u].first,rx=pt[u].first,ly=pt[u].second,ry=pt[u].second;
			int firstv=adj[u][d];
			T sr,sc;
			if(d==0){sr=pt[firstv].first;sc=pt[u].second;}
			else if(d==1){sr=pt[u].first;sc=pt[u].second;}
			else if(d==2){sr=pt[u].first;sc=pt[u].second-1;}
			else{sr=pt[u].first-1;sc=pt[firstv].second;}
			while(true){
				seen[u][d]=1;
				int v=adj[u][d];
				lx=min(lx,pt[v].first);rx=max(rx,pt[v].first);
				ly=min(ly,pt[v].second);ry=max(ry,pt[v].second);
				int nd=-1;
				int cand[4]={(d+1)%4,d,(d+3)%4,(d+2)%4};
				for(int z:cand)if(adj[v][z]!=-1){nd=z;break;}
				assert(nd!=-1);
				u=v;d=nd;
				if(u==s && d==sd)break;
			}
			bool inside=false;
			if(-TINF<sr && sr<TINF && -TINF<sc && sc<TINF)inside=covered(sr,sc);
			if(inside)ret.pb({lx,ly,rx-1,ry-1});
		}
		return ret;
	}

	void output()const{
		cout<<"RangeSet2D : ";
		for(auto ite=mp.begin();next(ite)!=mp.end();++ite){
			auto nxt=next(ite);
			if(ite->first==-TINF || nxt->first==TINF)continue;
			IV v;
			v.reserve(ycnt(ite->second));
			yintervals(ite->second,v);
			for(auto [l,r]:v)cout<<"["<<ite->first<<", "<<nxt->first-1<<"]x["<<l<<", "<<r<<"] ";
		}
		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;
}