제출 #605711

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
605711		rrrr10000	Rectangles (IOI19_rect)	C++14	100 / 100	2441 ms	940060 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));
	vvi rv(m,vi(n));
	rep(i,n)rep(j,m)rv[j][i]=v[i][j];
	REP(i,1,n-1){
		vi st;
		vi l(m,-1),r(m,m);
		rep(j,m){
			while(st.size()&&v[i][st.back()]<v[i][j]){
				r[st.back()]=j;st.pop_back();
			}
			if(st.size())l[j]=st.back();
			st.pb(j);
		}
		REP(j,1,m-1)if(l[j]!=-1&&r[j]!=m){
			if(v[i][l[j]]>v[i][j]&&v[i][r[j]]>v[i][j]){
				if(tate[l[j]+1][r[j]-1].size()==0||tate[l[j]+1][r[j]-1].back().se!=i-1)tate[l[j]+1][r[j]-1].pb(i,i);
				else tate[l[j]+1][r[j]-1].back().se++;
			}
		}
	}
	REP(i,1,m-1){
		vi st;
		vi l(n,-1),r(n,n);
		rep(j,n){
			while(st.size()&&rv[i][st.back()]<rv[i][j]){
				r[st.back()]=j;st.pop_back();
			}
			if(st.size())l[j]=st.back();
			st.pb(j);
		}
		REP(j,1,n-1)if(l[j]!=-1&&r[j]!=n){
			if(rv[i][l[j]]>rv[i][j]&&rv[i][r[j]]>rv[i][j]){
				if(yoko[l[j]+1][r[j]-1].size()==0||yoko[l[j]+1][r[j]-1].back().se!=i-1)yoko[l[j]+1][r[j]-1].pb(i,i);
				else yoko[l[j]+1][r[j]-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: 28 / 28