Submission #1243865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243865		hirayuu_oj	Rectangles (IOI19_rect)	C++20	72 / 100	5064 ms	846344 KiB

rect

#include "rect.h"

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) x.begin(),x.end()
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define fi first
#define se second
#define each(i,x) for(auto i:x)
using ll=long long;
/*
#include "grader.cpp"
/**/

template<class T,auto op,auto e>
struct SegTree{
	vector<T> val;
	int n;
	SegTree(int sz){
		n=sz;
		val.resize(n*2,e());
	}
	void set(int p,T v){
		p+=n;
		val[p]=v;
		while(p>1){
			p/=2;
			val[p]=op(val[p*2],val[p*2+1]);
		}
	}
	T prod(int l,int r){
		l+=n;
		r+=n;
		T rl=e(),rr=e();
		while(l<r){
			if(l&1){
				rl=op(rl,val[l]);l++;
			}
			if(r&1){
				r--;rr=op(val[r],rr);
			}
			l/=2;r/=2;
		}
		return op(rl,rr);
	}
};

ll mn(ll x,ll y){return min(x,y);}
ll mx(ll x,ll y){return max(x,y);}
ll emn(){
	return 1LL<<60;
}
ll emx(){
	return -(1LL<<60);
}

using seg=pair<int,int>;
int num(seg sm){
	return sm.fi*2502+sm.se;
}
ll rc_num(seg r,seg c){
	return num(r)*998244353LL+num(c);
}
const int X=2510*2510;
long long count_rectangles(std::vector<std::vector<int> > a) {
	int n=a.size();int m=a[0].size();
	vector<vector<seg>> r(n,vector<seg>(m,{-1,-1}));
	vector<vector<seg>> c(n,vector<seg>(m,{-1,-1}));
	rep(i,n){
		vector<pair<int,int>> pos(m);
		rep(j,m){
			pos[j]={a[i][j],j};
		}
		sort(all(pos)),reverse(all(pos));
		SegTree<ll,mn,emn> rmq(m);
		SegTree<ll,mx,emx> rMq(m);
		int cnt=0;
		rep(j,m){
			while(pos[j].fi!=pos[cnt].fi){
				rmq.set(pos[cnt].se,pos[cnt].se);
				rMq.set(pos[cnt].se,pos[cnt].se);
				cnt++;
			}
			ll lf=rMq.prod(0,pos[j].se);
			ll ri=rmq.prod(pos[j].se,m);
			if(lf<0||ri>m)continue;
			r[i][pos[j].se]={lf+1,ri};
		}
	}
	rep(i,m){
		vector<pair<int,int>> pos(n);
		rep(j,n){
			pos[j]={a[j][i],j};
		}
		sort(all(pos)),reverse(all(pos));
		SegTree<ll,mn,emn> rmq(n);
		SegTree<ll,mx,emx> rMq(n);
		int cnt=0;
		rep(j,n){
			while(pos[j].fi!=pos[cnt].fi){
				rmq.set(pos[cnt].se,pos[cnt].se);
				rMq.set(pos[cnt].se,pos[cnt].se);
				cnt++;
			}
			ll lf=rMq.prod(0,pos[j].se);
			ll ri=rmq.prod(pos[j].se,n);
			if(lf<0||ri>n)continue;
			c[pos[j].se][i]={lf+1,ri};
		}
	}
	unordered_set<ll> cand;
	vector<vector<int>> rr(X);
	rep(i,n){
		rep(j,m){
			if(r[i][j].fi!=-1&&(rr[num(r[i][j])].empty()||rr[num(r[i][j])].back()!=i)){
				rr[num(r[i][j])].push_back(i);
			}
		}
	}
	
	vector<vector<int>> cc(X);
	rep(i,m){
		rep(j,n){
			if(c[j][i].fi!=-1&&(cc[num(c[j][i])].empty()||cc[num(c[j][i])].back()!=i)){
				cc[num(c[j][i])].push_back(i);
			}
		}
	}
	ll ret=0;
	rep(i,n){
		rep(j,m){
			if(r[i][j].fi!=-1&&c[i][j].fi!=-1){
				ll nm=rc_num(r[i][j],c[i][j]);
				if(!cand.count(nm)){
					cand.insert(nm);
					int m1=lower_bound(all(cc[num(c[i][j])]),r[i][j].fi)-cc[num(c[i][j])].begin();
					int m2=lower_bound(all(cc[num(c[i][j])]),r[i][j].se)-cc[num(c[i][j])].begin();
					if(r[i][j].se-r[i][j].fi!=m2-m1)continue;
					m1=lower_bound(all(rr[num(r[i][j])]),c[i][j].fi)-rr[num(r[i][j])].begin();
					m2=lower_bound(all(rr[num(r[i][j])]),c[i][j].se)-rr[num(r[i][j])].begin();
					if(c[i][j].se-c[i][j].fi!=m2-m1)continue;
					ret++;
				}
			}
		}
	}
	
	/*
	*/
	return ret;
}

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28