Submission #443350

#	Time	Username	Problem	Language	Result	Execution time	Memory
443350		vanic	Rectangles (IOI19_rect)	C++14	37 / 100	5099 ms	576656 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 mod=1e9+7, p=2503;

inline int sum(int a, int b){
	if(a+b>=mod){
		return a+b-mod;
	}
	if(a+b<0){
		return a+b+mod;
	}
	return a+b;
} 

inline int mul(int a, int b){
	return (ll)a*b%mod;
}

inline int pretvori(int a[4]){
	int br=0;
	for(int i=0; i<4; i++){
		br=mul(br, p);
		br=sum(br, a[i]);
	}
	return br;
}
 
const int maxn=2505, Log=12, pot=(1<<Log);
const int inf=1e9;

struct tmin{
	int t[pot*2];
	tmin(){
		for(int i=0; i<pot*2; i++){
			t[i]=inf;
		}
	}
	void update(int x, int val){
		t[x]=val;
		for(x/=2; x>0; x/=2){
			t[x]=min(t[x*2], t[x*2+1]);
		}
	}
	int query(int L, int D, int x, int l, int d){
		if(L>=l && D<=d){
			return t[x];
		}
		int lijeva=inf, desna=inf;
		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);
		}
		return min(lijeva, desna);
	}
};

struct tmax{
	int t[pot*2];
	void update(int x, int val){
		t[x]=val;
		for(x/=2; x>0; x/=2){
			t[x]=max(t[x*2], t[x*2+1]);
		}
	}
	int query(int L, int D, int x, int l, int d){
		if(L>=l && D<=d){
			return t[x];
		}
		int lijeva=0, desna=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);
		}
		return max(lijeva, desna);
	}
};

tmin R1[maxn], C1[maxn];
tmax R2[maxn], C2[maxn];
 

ll sol;
int svi[maxn][maxn][4];
int n, m;
map < int, bool > bio;
int svi1[maxn][maxn][4];
 
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()){
				svi1[i][j][2]=0;
			}
			else{
				svi1[i][j][2]=v.back().second+1;
			}


			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()){
				svi1[i][j][3]=m-1;
			}
			else{
				svi1[i][j][3]=v.back().second-1;
			}
			
			
			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()){
				svi1[i][j][0]=0;
			}
			else{
				svi1[i][j][0]=v.back().second+1;
			}



			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()){
				svi1[i][j][1]=n-1;
			}
			else{
				svi1[i][j][1]=v.back().second-1;
			}


			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++){
			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]);
		}
	}
	int c[4];
	int br;
//	array < int, 4 > b;
	for(int i=1; i<n-1; i++){
		for(int j=1; j<m-1; j++){
			for(int k=0; k<4; k++){
				c[k]=svi[i][j][k];
			}
			br=pretvori(c);
			if(c[0]==0 || c[2]==0 || c[1]==n-1 || c[3]==m-1 || bio[br]){
				continue;
			}
/*			if(i==1 && j==1){
				cout << R1[c[1]+1].query(0, pot-1, 1, c[2], c[3]) << endl;
			}*/
			if(c[0]<R2[c[1]+1].query(0, pot-1, 1, c[2], c[3])){
				continue;
			}
			if(c[1]>R1[c[0]-1].query(0, pot-1, 1, c[2], c[3])){
				continue;
			}
			if(c[2]<C2[c[3]+1].query(0, pot-1, 1, c[0], c[1])){
				continue;
			}
			if(c[3]>C1[c[2]-1].query(0, pot-1, 1, c[0], c[1])){
				continue;
			}
			bio[br]=1;
//			cout << c[0] << ' '<< c[2] << ' ' << c[1] << ' ' << c[3] << endl;
			sol++;
		}
	}
	return sol;
}

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