Submission #443288

#	Time	Username	Problem	Language	Result	Execution time	Memory
443288		vanic	Rectangles (IOI19_rect)	C++14	49 / 100	2210 ms	1048580 KiB

rect

#include "rect.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <array>

using namespace std;

typedef long long ll;

const int maxn=705, Log=10, pot=(1<<Log);
const int inf=1e9;


struct tournament{
	struct segment{
		array < int, 4 > t[pot*2];
		segment(){
			array < int, 4 > a={inf, 0, inf, 0};
			for(int i=0; i<pot*2; i++){
				t[i]=a;
			}
		}
		void update(int x, array < int, 4 > val){
			t[x][0]=min(t[x][0], val[0]);
			t[x][1]=max(t[x][1], val[1]);
			t[x][2]=min(t[x][2], val[2]);
			t[x][3]=max(t[x][3], val[3]);
//			cout << "upd " << x << endl;
			for(x/=2; x>0; x/=2){
				t[x][0]=min(t[x*2][0], t[x*2+1][0]);
				t[x][1]=max(t[x*2][1], t[x*2+1][1]);
				t[x][2]=min(t[x*2][2], t[x*2+1][2]);
				t[x][3]=max(t[x*2][3], t[x*2+1][3]);
			}
		}
		array < int, 4 > query(int L, int D, int x, int l, int d){
			if(L>=l && D<=d){
				return t[x];
			}
			array < int, 4 > lijeva={inf, 0, inf, 0}, desna={inf, 0, inf, 0};
			if((L+D)/2>=l){
				lijeva=query(L, (L+D)/2, x*2, l, d);
			}
			if((L+D)/2+1<=d){
				desna=query((L+D)/2+1, D, x*2+1, l, d);
			}
			lijeva[0]=min(lijeva[0], desna[0]);
			lijeva[1]=max(lijeva[1], desna[1]);
			lijeva[2]=min(lijeva[2], desna[2]);
			lijeva[3]=max(lijeva[3], desna[3]);
			return lijeva;
		}
	};
	segment s[pot*2];
	void update(int x, int y, array < int, 4 > val){
		x+=pot;
		y+=pot;
		for(; x>0; x/=2){
			s[x].update(y, val);
		}
	}
	array < int, 4 > query(int L, int D, int x, int l, int d, int l2, int d2){
		if(L>=l && D<=d){
			return s[x].query(0, pot-1, 1, l2, d2);
		}
		array < int, 4 > lijeva={inf, 0, inf, 0}, desna={inf, 0, inf, 0};
		if((L+D)/2>=l){
			lijeva=query(L, (L+D)/2, x*2, l, d, l2, d2);
		}
		if((L+D)/2+1<=d){
			desna=query((L+D)/2+1, D, x*2+1, l, d, l2, d2);
		}
		lijeva[0]=min(lijeva[0], desna[0]);
		lijeva[1]=max(lijeva[1], desna[1]);
		lijeva[2]=min(lijeva[2], desna[2]);
		lijeva[3]=max(lijeva[3], desna[3]);
		return lijeva;
	}
};

tournament T;
ll sol;
array < int, 4 > svi[maxn][maxn];
int n, m;
map < array < int, 4 >, bool > bio;

ll count_rectangles(vector < vector < int > > a){
	n=a.size();
	m=a[0].size();
	vector < pair <int, int > > v;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			while(!v.empty() && v.back().first<=a[i][j]){
				v.pop_back();
			}
			if(v.empty()){
				svi[i][j][2]=0;
			}
			else{
				svi[i][j][2]=v.back().second+1;
			}
			v.push_back({a[i][j], j});
		}
		v.clear();
		for(int j=m-1; j>-1; j--){
			while(!v.empty() && v.back().first<=a[i][j]){
				v.pop_back();
			}
			if(v.empty()){
				svi[i][j][3]=m-1;
			}
			else{
				svi[i][j][3]=v.back().second-1;
			}
			v.push_back({a[i][j], j});
		}
		v.clear();
	}
	for(int j=0; j<m; j++){
		for(int i=0; i<n; i++){
			while(!v.empty() && v.back().first<=a[i][j]){
				v.pop_back();
			}
			if(v.empty()){
				svi[i][j][0]=0;
			}
			else{
				svi[i][j][0]=v.back().second+1;
			}
			v.push_back({a[i][j], i});
		}
		v.clear();
		for(int i=n-1; i>-1; i--){
			while(!v.empty() && v.back().first<=a[i][j]){
				v.pop_back();
			}
			if(v.empty()){
				svi[i][j][1]=n-1;
			}
			else{
				svi[i][j][1]=v.back().second-1;
			}
			v.push_back({a[i][j], i});
		}
		v.clear();
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
/*			for(int k=0; k<4; k++){
				cout << svi[i][j][k] << ' ';
			}
			cout << endl;*/
			T.update(i, j, svi[i][j]);
		}
	}
	array < int, 4 > c;
	array < int, 4 > b;
	for(int i=1; i<n-1; i++){
		for(int j=1; j<m-1; j++){
			c=svi[i][j];
			if(c[0]==0 || c[2]==0 || c[1]==n-1 || c[3]==m-1){
				continue;
			}
			b=T.query(0, pot-1, 1, c[0], c[1], c[2], c[3]);
			if(c==b && !bio[b]){
//				cout << c[0] << ' ' << c[2] << ' ' << c[1] << ' ' << c[3] << endl;
				sol++;
				bio[b]=1;
			}
/*			cout << i << ' ' << j << endl;
			for(int k=0; k<4; k++){
				cout << c[k] << ' ';
			}
			cout << endl;
			for(int k=0; k<4; k++){
				cout << b[k] << ' ';
			}
			cout << endl << endl;*/
		}
	}
	return sol;
}

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