Submission #434339

#	Time	Username	Problem	Language	Result	Execution time	Memory
434339		lakshith_	Rectangles (IOI19_rect)	C++14	15 / 100	5044 ms	480720 KiB

rect

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

using namespace std;

#define int long long
#define what_is(a) cerr << #a << " is " << a << endl
#define checker(a) cerr << "checker reached " << a << endl
#define cout cerr

const int MAXN = 1e3+1;
const int K = 25;

//sparce table
struct sparce{

	int log[MAXN+1];
	
	int st[MAXN][K + 1];
	
	int N;
	
	void init(vector<int> array){
		N = array.size();
		log[1] = 0;
		for (int i = 2; i <= MAXN; i++)
			log[i] = log[i/2] + 1;
			
		for (int i = 0; i < N; i++)
			st[i][0] = array[i];

		for (int j = 1; j <= K; j++)
			for (int i = 0; i + (1 << j) <= N; i++)
				st[i][j] = max(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
	}
	
	int getMax(int L,int R){
		int j = log[R - L + 1];
		return max(st[L][j], st[R - (1 << j) + 1][j]);
	}

};

sparce rows[1000],cols[1000];

bool check(int r1,int c1,int r2,int c2,vector<vector<signed>>& a){
	for(int i=r1;i<=r2;i++){
		//what_is(i);
		int r = rows[i].getMax(c1,c2);
		//cout <<c1 << " " << c2 << endl;
		//what_is(r);
		if(r>=a[i][c1-1]||r>=a[i][c2+1])return false;
	}
	for(int j=c1;j<=c2;j++){
		int r = cols[j].getMax(r1,r2);
		if(r>=a[r1-1][j]||r>=a[r2+1][j])return false;
	}
	return true;
}

long long count_rectangles(std::vector<std::vector<signed> > a) {
	int n = a.size(),m=a[0].size();
	//what_is(n);
	vector<int> vec;
	//precompute sparce
	for(int i=0;i<n;i++){
		vec.clear();
		for(int j=0;j<m;j++)
			vec.push_back(a[i][j]);
		rows[i].init(vec);
	}
	for(int j=0;j<m;j++){
		vec.clear();
		for(int i=0;i<n;i++)
			vec.push_back(a[i][j]);
		cols[j].init(vec);
	}
	int ans = 0;
	for(int r1=1;r1<n-1;r1++)
		for(int c1=1;c1<m-1;c1++)
			for(int r2=r1;r2<n-1;r2++)
				for(int c2=c1;c2<m-1;c2++){
					//cout << r1 << " " << r2 << "\n";
					ans += check(r1,c1,r2,c2,a);
				}
	return ans;
}

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