Submission #443546

#	Time	Username	Problem	Language	Result	Execution time	Memory
443546		vanic	Rectangles (IOI19_rect)	C++14	100 / 100	3462 ms	574944 KiB

rect

#include "rect.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
 
using namespace std;
 
typedef long long ll;
 
const int maxn=2503, Log=12, pot=(1<<Log);
const int inf=1e9;
ll sol;
int svi[maxn][maxn][4];
int n, m;
ll bio[maxn*maxn];
int svi1[maxn][maxn][4];


struct tmin{
	int t[pot*2];
	void update(int x, int val){
		t[x]=val;
	}
	void gradi(){
		for(int x=pot-1; x>0; x--){
			t[x]=min(t[x*2], t[x*2+1]);
		}
	}
	int query(int l, int r){
		int sol=inf;
		for(l+=pot, r+=pot; l<r; l>>=1, r>>=1){
			if(l&1){
				sol=min(sol, t[l++]);
			}
			if(r&1){
				sol=min(sol, t[--r]);
			}
		}
		return sol;
	}
};
 
struct tmax{
	int t[pot*2];
	void update(int x, int val){
		t[x]=val;
	}
	void gradi(){
		for(int x=pot-1; x>0; x--){
			t[x]=max(t[x*2], t[x*2+1]);
		}
	}
	int query(int l, int r){
		int sol=0;
		for(l+=pot, r+=pot; l<r; l>>=1, r>>=1){
			if(l&1){
				sol=max(sol, t[l++]);
			}
			if(r&1){
				sol=max(sol, t[--r]);
			}
		}
		return sol;
	}
};
 
tmin R1[maxn], C1[maxn];
tmax R2[maxn], C2[maxn];
pair < int, int > v[maxn];

 
ll count_rectangles(vector < vector < int > > a){
	n=a.size();
	m=a[0].size();
	int indeks=0;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			while(indeks && v[indeks-1].first<a[i][j]){
				indeks--;
			}
			if(!indeks){
				svi1[i][j][2]=0;
			}
			else{
				svi1[i][j][2]=v[indeks-1].second+1;
			}
 
 
			while(indeks && v[indeks-1].first<=a[i][j]){
				indeks--;
			}
			if(!indeks){
				svi[i][j][2]=0;
			}
			else{
				svi[i][j][2]=v[indeks-1].second+1;
			}
			v[indeks]={a[i][j], j};
			indeks++;
		}
		indeks=0;
		for(int j=m-1; j>-1; j--){
			while(indeks && v[indeks-1].first<a[i][j]){
				indeks--;
			}
			if(!indeks){
				svi1[i][j][3]=m-1;
			}
			else{
				svi1[i][j][3]=v[indeks-1].second-1;
			}
			
			
			while(indeks && v[indeks-1].first<=a[i][j]){
				indeks--;
			}
			if(!indeks){
				svi[i][j][3]=m-1;
			}
			else{
				svi[i][j][3]=v[indeks-1].second-1;
			}
			v[indeks]={a[i][j], j};
			indeks++;
		}
		indeks=0;
	}
	for(int j=0; j<m; j++){
		for(int i=0; i<n; i++){
			while(indeks && v[indeks-1].first<a[i][j]){
				indeks--;
			}
			if(!indeks){
				svi1[i][j][0]=0;
			}
			else{
				svi1[i][j][0]=v[indeks-1].second+1;
			}
 
 
 
			while(indeks && v[indeks-1].first<=a[i][j]){
				indeks--;
			}
			if(!indeks){
				svi[i][j][0]=0;
			}
			else{
				svi[i][j][0]=v[indeks-1].second+1;
			}
			v[indeks]={a[i][j], i};
			indeks++;
		}
		indeks=0;
		for(int i=n-1; i>-1; i--){
			while(indeks && v[indeks-1].first<a[i][j]){
				indeks--;
			}
			if(!indeks){
				svi1[i][j][1]=n-1;
			}
			else{
				svi1[i][j][1]=v[indeks-1].second-1;
			}
 
 
			while(indeks && v[indeks-1].first<=a[i][j]){
				indeks--;
			}
			if(!indeks){
				svi[i][j][1]=n-1;
			}
			else{
				svi[i][j][1]=v[indeks-1].second-1;
			}
			v[indeks]={a[i][j], i};
			indeks++;
		}
		indeks=0;
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			R1[i].update(j+pot, svi1[i][j][1]);
			R2[i].update(j+pot, svi1[i][j][0]);
			C1[j].update(i+pot, svi1[i][j][3]);
			C2[j].update(i+pot, svi1[i][j][2]);
		}
	}
	for(int i=0; i<n; i++){
		R1[i].gradi();
		R2[i].gradi();
	}
	for(int i=0; i<m; i++){
		C1[i].gradi();
		C2[i].gradi();
	}
	int c[4];
	ll br;
	indeks=0;
	for(int i=1; i<n-1; i++){
		for(int j=1; j<m-1; j++){
			br=0;
			for(int k=0; k<4; k++){
				c[k]=svi[i][j][k];
				br*=maxn;
				br+=c[k];
			}
			if(c[0]==0 || c[2]==0 || c[1]==n-1 || c[3]==m-1){
				continue;
			}
			if(c[0]<R2[c[1]+1].query(c[2], c[3]+1)){
				continue;
			}
			if(c[1]>R1[c[0]-1].query(c[2], c[3]+1)){
				continue;
			}
			if(c[2]<C2[c[3]+1].query(c[0], c[1]+1)){
				continue;
			}
			if(c[3]>C1[c[2]-1].query(c[0], c[1]+1)){
				continue;
			}
//			cout << c[0] << ' '<< c[2] << ' ' << c[1] << ' ' << c[3] << endl;
			bio[indeks]=br;
			indeks++;
		}
	}
	sort(bio, bio+indeks);
	for(int i=0; i<indeks; i++){
		if(i==indeks-1 || bio[i]!=bio[i+1]){
			sol++;
		}
	}
	return sol;
}

• 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