제출 #422904

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
422904		MeGustaElArroz23	Rectangles (IOI19_rect)	C++14	50 / 100	5097 ms	184196 KiB

rect

#include "rect.h"
#include <cstdio>
#include <unistd.h>
#include <cassert>
#include <string>

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<ll,ll> pii;
typedef vector<pii> vii;
typedef vector<vii> vvii;
const ll INF=1000000001;

//struct node{
//	ll l;
//	ll r;
//	ll left;
//	ll right;
//	ll minimo;
//}
//ll counter;
//void create_tree(ll ind1, ll ind2, ll l, ll r){
//	st[ind1][ind2][counter].l=l;
//	st[ind1][ind2][counter].l=r;
//	if (l!=r){
//		ll menor;
//		ll ind3=counter;
//		counter++;
//		st[ind1][ind2][ind3].left=counter;
//		menor=min(menor,create_tree(ind1,ind2,l,(l+r)/2));
//		counter++;
//		st[ind1][ind2][ind3].right=counter;
//		menor=min(menor,create_tree(ind1,ind2,(l+r)/2+1,r);
//	}
//	else{
//		if (ind1==1) return
//	}
//}

//vector<vector<vector<node>>> st;

bool esbinario (vvi v){
	for (vi x:v){
		for (int y:x){
			if (y>1) return false;
		}
	}
	return true;
}

ll casobinario(vvi v){
	//cerr<<"a";
	ll n=v.size();
	ll m=v[0].size();
	vvii g(n,vii(m,pii{0,0}));
	for (ll i=1;i<n-1;i++){
		for (ll j=1;j<m-1;j++){
			if (v[i][j]==1) continue;
			if (v[i-1][j]==1){
				ll x=i;
				while (x<n and v[x][j]==0) x++;
				x--;
				if (x!=n) g[i][j].first=x;
			}
			if (v[i][j-1]==1){
				ll x=j;
				while (x<m and v[i][x]==0) x++;
				x--;
				if (x!=m) g[i][j].second=x;
			}
		}
	}
	//cerr << g[1][2].first << ' ' << g[1][2].second << '\n';
	ll sol=0;
	for (ll i=1;i<n-1;i++){
		for (ll j=1;j<m-1;j++){
			if (g[i][j].first and g[i][j].second){
				bool T=true;
				for (ll a=i;a<=g[i][j].first;a++){
					if (g[a][j].second!=g[i][j].second){
						T=false;
						break;
					}
				}
				if (T){
					for (ll a=j;a<=g[i][j].second;a++){
						if (g[i][a].first!=g[i][j].first){
							T=false;
							break;
						}
					}
				}
				if (T){
					//cerr << i << ' ' << j << '\n';
					sol++;
				}
			}
		}
	}
	return sol;
}

long long count_rectangles(std::vector<std::vector<int> > v) {
	if(esbinario(v)) return casobinario(v);
	ll sol=0;
	ll n=v.size();
	ll m=v[0].size();
	//st=vector<vector<vector<node>>>(2,vector<vector<node>>(1000),vector<node>(2000));
	//vvvi;
	for (ll i1=1;i1<n-1;i1++){
		for (ll j1=1;j1<m-1;j1++){
			if (v[i1][j1]>=min(v[i1-1][j1],v[i1][j1-1])) continue;
			for (ll i2=i1;i2<n-1;i2++){
				for (ll j2=j1;j2<m-1;j2++){
					bool T=true;
					for (ll x=i1;x<=i2;x++){
						for (ll y=j1;y<=j2;y++){
							if (v[x][y]>=min(min(v[i1-1][y],v[i2+1][y]),min(v[x][j1-1],v[x][j2+1]))){
								T=false;
								break;
							}
						}
						if (T==false) break;
					}
					//ll menor=INF;
					//for (ll x=i1;x<=i2;x++) menor=min(menor,min(v[x][j1-1],v[x][j2+1]));
					//for (ll x=j1;x<=j2;x++) menor=min(menor,min(v[i1-1][x],v[i2+1][x]));
					//if (vi{i1,i2,j1,j2}==vi{1,2,1,1}) cerr << mayor << ' '<<menor<<'\n';
					//if (mayor<menor){
					//	sol++;
						//cerr << i1<<' '<<i2<<' '<<j1<<' '<<j2<<' '<<mayor<<' '<<menor<<'\n';
					//} 
					if (T){
						sol++;
						//cerr<<i1<<' '<<i2<<' '<<j1<<' '<<j2<<'\n';
					}
				}
			}
		}
	}
	return sol;
}

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