Submission #605701

#	Time	Username	Problem	Language	Result	Execution time	Memory
605701		rrrr10000	Rectangles (IOI19_rect)	C++14	72 / 100	5109 ms	852884 KiB

rect

#include "rect.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define fi first
#define se second
#define pb emplace_back
template<class T> void out(T a){cout<<a<<endl;}

long long count_rectangles(std::vector<std::vector<int> > v) {
	ll n=v.size(),m=v[0].size();
	vvvp tate(m,vvp(m)),yoko(n,vvp(n));
	REP(i,1,n-1){
		vp srt;
		rep(j,m)srt.pb(v[i][j],j);
		rsort(srt);
		set<ll> S;
		for(auto x:srt){
			auto itr=S.insert(x.se).fi;
			if(itr==S.begin())continue;
			itr--;
			ll l=*itr;
			itr++;itr++;
			if(itr==S.end())continue;
			ll r=*itr;
			if(v[i][l]>x.fi&&v[i][r]>x.fi){
				if(tate[l+1][r-1].size()==0||tate[l+1][r-1].back().se!=i-1)tate[l+1][r-1].pb(i,i);
				else tate[l+1][r-1].back().se++;
			}
		}
	}
	REP(i,1,m-1){
		vp srt;
		rep(j,n)srt.pb(v[j][i],j);
		rsort(srt);
		set<ll> S;
		for(auto x:srt){
			auto itr=S.insert(x.se).fi;
			if(itr==S.begin())continue;
			itr--;
			ll l=*itr;
			itr++;itr++;
			if(itr==S.end())continue;
			ll r=*itr;
			if(v[l][i]>x.fi&&v[r][i]>x.fi){
				if(yoko[l+1][r-1].size()==0||yoko[l+1][r-1].back().se!=i-1)yoko[l+1][r-1].pb(i,i);
				else yoko[l+1][r-1].back().se++;
			}
		}
	}
	vvvp tmp(n,vvp(m));
	rep(l,n)rep(r,n)for(auto rng:yoko[l][r]){
		REP(i,rng.fi,rng.se+1)tmp[l][i].pb(r,rng.se);
	}
	ll ans=0;
	rep(l,m)rep(r,m)for(auto rng:tate[l][r]){
		REP(i,rng.fi,rng.se+1){
			for(auto x:tmp[i][l]){
				if(x.fi>rng.se)break;
				if(x.se>=r)ans++;
			}
		}
	}
	return ans;
}

• 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