Submission #823664

#	Time	Username	Problem	Language	Result	Execution time	Memory
823664		oscar1f	Rectangles (IOI19_rect)	C++17	0 / 100	5082 ms	483656 KiB

rect

#include<bits/stdc++.h>
#include "rect.h"

using namespace std;
using ll=long long;

const int TAILLE_MAX=2505,DECA=(1<<12),INFINI=1000*1000*1000;
ll rep;
int nbLig,nbCol;
int val[TAILLE_MAX][TAILLE_MAX];
int limite[TAILLE_MAX][TAILLE_MAX][4];
int limCalc[TAILLE_MAX][2];
int arbreMin[TAILLE_MAX][2*DECA],arbreMax[TAILLE_MAX][2*DECA],arbreSom[2*DECA];
vector<int> possi;
set<int> enCours;
set<int>::iterator it;
vector<int> prop[TAILLE_MAX][TAILLE_MAX];

int calcMin(int tab,int deb,int fin) {
	if (deb==fin) {
		return arbreMin[tab][deb];
	}
	if (deb%2==1) {
		return min(arbreMin[tab][deb],calcMin(tab,deb+1,fin));
	}
	if (fin%2==0) {
		return min(arbreMin[tab][fin],calcMin(tab,deb,fin-1));
	}
	return calcMin(tab,deb/2,fin/2);
}

int calcMax(int tab,int deb,int fin) {
	if (deb==fin) {
		return arbreMax[tab][deb];
	}
	if (deb%2==1) {
		return max(arbreMax[tab][deb],calcMax(tab,deb+1,fin));
	}
	if (fin%2==0) {
		return max(arbreMax[tab][fin],calcMax(tab,deb,fin-1));
	}
	return calcMax(tab,deb/2,fin/2);
}

int calcSom(int deb,int fin) {
	if (deb==fin) {
		return arbreSom[deb];
	}
	if (deb%2==1) {
		return arbreSom[deb]+calcSom(deb+1,fin);
	}
	if (fin%2==0) {
		return arbreSom[fin]+calcSom(deb,fin-1);
	}
	return calcSom(deb/2,fin/2);
}

void ajout(int pos,int coeff) {
	pos+=DECA;
	arbreSom[pos]+=coeff;
	while (pos>1) {
		pos/=2;
		arbreSom[pos]=arbreSom[2*pos]+arbreSom[2*pos+1];
	}
}

void calc(int ligHaut,int ligBas,int colGau,int colDroi) {
	//cout<<ligHaut<<" "<<ligBas<<" "<<colGau<<" "<<colDroi<<" : ";
	for (int i=colGau-1;i<=colDroi+1;i++) {
		limCalc[i][0]=calcMax(i,DECA+ligHaut,DECA+ligBas);
		limCalc[i][1]=calcMin(i,DECA+ligHaut,DECA+ligBas);
		//cout<<i<<" "<<limCalc[i][0]<<" "<<limCalc[i][1]<<"   ";
	}
	//cout<<endl;
	vector<tuple<int,int,int>> listeCol;
	for (int i=colGau-1;i<=colDroi+1;i++) {
		listeCol.push_back(make_tuple(i,1,i));
		listeCol.push_back(make_tuple(limCalc[i][0]-1,-1,i));
	}
	sort(listeCol.begin(),listeCol.end(),[&](tuple<int,int,int> a,tuple<int,int,int> b) {
		if (get<0>(a)>get<0>(b)) {
			return true;
		}
		if (get<0>(a)<get<0>(b)) {
			return false;
		}
		return get<0>(a)>get<0>(b);
	});
	for (auto k:listeCol) {
		//cout<<get<0>(k)<<" "<<get<1>(k)<<" "<<get<2>(k)<<"   ";
		if (get<1>(k)==-1) {
			ajout(get<2>(k),-1);
		}
		else {
			if (limCalc[get<0>(k)][1]+1>=get<0>(k)+2) {
				//cout<<"!";
				rep+=(ll)calcSom(DECA+get<0>(k)+2,DECA+limCalc[get<0>(k)][1]+1);
			}
			ajout(get<0>(k),1);
		}
	}
	//cout<<endl;
}

ll count_rectangles(vector<vector<int>> a) {
	nbLig=a.size();
	nbCol=a[0].size();
	if (nbLig<=2 or nbCol<=2) {
		return 0;
	}
	for (int i=0;i<nbLig;i++) {
		for (int j=0;j<nbCol;j++) {
			val[i][j]=a[i][j];
		}
	}
	for (int i=0;i<nbLig;i++) {
		enCours.clear();
		enCours.insert(-1);
		possi.clear();
		for (int j=0;j<nbCol;j++) {
			possi.push_back(j);
		}
		sort(possi.begin(),possi.end(),[&](int a,int b) {
			if (val[i][a]>val[i][b]) {
				return true;
			}
			if (val[i][a]<val[i][b]) {
				return false;
			}
			return a<b;
		});
		for (int j:possi) {
			it=enCours.upper_bound(j);
			it--;
			limite[i][j][0]=(*it)+1;
			//cout<<i<<" "<<j<<" : "<<limite[i][j][0]<<endl;
			enCours.insert(j);
		}
		enCours.clear();
		enCours.insert(nbCol);
		sort(possi.begin(),possi.end(),[&](int a,int b) {
			if (val[i][a]>val[i][b]) {
				return true;
			}
			if (val[i][a]<val[i][b]) {
				return false;
			}
			return a>b;
		});
		for (int j:possi) {
			it=enCours.upper_bound(j);
			limite[i][j][1]=(*it)-1;
			//cout<<i<<" "<<j<<" : "<<limite[i][j][0]<<endl;
			enCours.insert(j);
		}
	}
	for (int j=0;j<nbCol;j++) {
		enCours.clear();
		enCours.insert(-1);
		possi.clear();
		for (int i=0;i<nbLig;i++) {
			possi.push_back(i);
		}
		sort(possi.begin(),possi.end(),[&](int a,int b) {
			if (val[a][j]>val[b][j]) {
				return true;
			}
			if (val[a][j]<val[b][j]) {
				return false;
			}
			return a<b;
		});
		for (int i:possi) {
			it=enCours.upper_bound(i);
			it--;
			limite[i][j][2]=(*it)+1;
			//cout<<i<<" "<<j<<" : "<<limite[i][j][0]<<endl;
			enCours.insert(i);
		}
		enCours.clear();
		enCours.insert(nbLig);
		sort(possi.begin(),possi.end(),[&](int a,int b) {
			if (val[a][j]>val[b][j]) {
				return true;
			}
			if (val[a][j]<val[b][j]) {
				return false;
			}
			return a>b;
		});
		for (int i:possi) {
			it=enCours.upper_bound(i);
			limite[i][j][3]=(*it)-1;
			//cout<<i<<" "<<j<<" : "<<limite[i][j][0]<<endl;
			enCours.insert(i);
		}
	}
	int deb,pos;
	for (int i=0;i<nbCol;i++) {
		for (int j=0;j<2*DECA;j++) {
			arbreMin[i][j]=nbCol-1;
			arbreMax[i][j]=0;
		}
		for (int j=0;j<nbLig;j++) {
			arbreMin[i][DECA+j]=limite[j][i][1];
			arbreMax[i][DECA+j]=limite[j][i][0];
		}
		for (int j=DECA-1;j>0;j--) {
			arbreMin[i][j]=min(arbreMin[i][2*j],arbreMin[i][2*j+1]);
			arbreMax[i][j]=max(arbreMax[i][2*j],arbreMax[i][2*j+1]);
		}
	}
	possi.clear();
	for (int i=0;i<nbLig;i++) {
		possi.push_back(i);
	}
	int lig;
	for (int col=1;col<nbCol-1;col++) {
		enCours.clear();
		enCours.insert(-INFINI);
		enCours.insert(INFINI);
		sort(possi.begin(),possi.end(),[&](int a,int b) {
			if (val[a][col]>val[b][col]) {
				return true;
			}
			if (val[a][col]<val[b][col]) {
				return false;
			}
			return a<b;
		});
		//cout<<col<<" : ";
		for (int i=0;i<nbLig;i++) {
			lig=possi[i];
			//cout<<lig<<" ";
			it=enCours.upper_bound(lig);
			if ((*it)!=INFINI and (*it)-lig>1 and (i==nbLig-1 or val[possi[i]][col]>val[possi[i+1]][col] or possi[i+1]>(*it))) {
				//cout<<"! "<<lig+1<<" "<<(*it)-1<<" "<<col<<endl;
				prop[lig+1][(*it)-1].push_back(col);
			}
			it--;
			if ((*it)!=-INFINI and lig-(*it)>1) {
				prop[(*it)+1][lig-1].push_back(col);
				//cout<<"! "<<(*it)+1<<" "<<lig-1<<" "<<col<<endl;
			}
			enCours.insert(lig);
		}
		//cout<<endl;
	}

	for (int ligHaut=1;ligHaut<nbLig-1;ligHaut++) {
		for (int ligBas=ligHaut;ligBas<nbLig-1;ligBas++) {
			prop[ligHaut][ligBas].push_back(INFINI);
			pos=0;
			while (prop[ligHaut][ligBas][pos]!=INFINI) {
				deb=pos;
				while (prop[ligHaut][ligBas][pos]!=INFINI and prop[ligHaut][ligBas][pos+1]==prop[ligHaut][ligBas][pos]+1) {
					pos++;
				}
				calc(ligHaut,ligBas,prop[ligHaut][ligBas][deb],prop[ligHaut][ligBas][pos]);
				pos++;
			}
		}
	}
	return rep;
}

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