Submission #158676

#	Time	Username	Problem	Language	Result	Execution time	Memory
158676		LordOfIran	Rectangles (IOI19_rect)	C++14	Compilation error	0 ms	0 KiB

rect

//                             In The Name Of Allah
#include "rect.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
#define ss second
#define ff first
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ret(n) return cout << n, 0
#define se(n) cout << setprecision(n) << fixed
#define pb push_back
using namespace std; 

const long long N = 210, OO = 1e12 + 7, M = 1e9 + 7, M2 = 998244353, sq = 360, lg = 23;
typedef pair <int, int> pii; 
int bad[N][N][10], n, m, mn[N][N][N];
vector <vector <int> > a;

void get1(int i) {
	vector <int> v;
	for(int j = 0; j < m; j++) {
		while(v.size()) {
			if(a[i][v[v.size() - 1]] < a[i][j])
				v.pop_back();
			else
				break;
		}
		if(v.size()) 
			bad[i][j][0] = v[v.size() - 1];
		v.pb(j);
	}
	v.clear();
	for(int j = m - 1; j >= 0; j--) {
		while(v.size()) {
			if(a[i][v[v.size() - 1]] < a[i][j])
				v.pop_back();
			else
				break;	
		}
		if(v.size())
			bad[i][j][1] = v[v.size() - 1];
		else
			bad[i][j][1] = m;
		v.pb(j);
	}
}

void get2(int j) {
	vector <int> v;
	for(int i = 0; i < n; i++) {
		while(v.size()) {
			if(a[v[v.size() - 1]][j] < a[i][j])
				v.pop_back();
			else
				break;	
		}
		if(v.size())
			bad[i][j][2] = v[v.size() - 1];
		v.pb(i);
	}
	v.clear();
	for(int i = n - 1; i >= 0; i--) {
		while(v.size()) {
			if(a[v[v.size() - 1]][j] < a[i][j])
				v.pop_back();
			else
				break;	
		}
		if(v.size())
			bad[i][j][3] = v[v.size() - 1];
		else
			bad[i][j][3] = n;
		v.pb(i);
	}
}

int count_rectangles(vector<vector <int> > b) {
	a = b;
	n = (int)a.size(), m = (int)a[0].size();
	for(int i = 0; i < n; i++) 
		get1(i);
	for(int j = 0; j < m; j++) 
		get2(j);
	for(int k = 1; k < m; k++) {
		for(int i = 1; i < n; i++) {
			mn[k][i][i] = bad[i][k][0];
			for(int j = i + 1; j < n - 1; j++) 
				mn[k][i][j] = max(mn[k][i][j - 1], bad[j][k][0]);
		}
	}
	int ans = 0;
	for(int k = 0; k < m - 2; k++) {
		for(int i = 1; i < n - 1; i++) {
			int mi = OO;
			for(int j = i; j < n - 1; j++) {
				mi = min(mi, bad[j][k][1]);
				int mk = OO, ml = 0; 
				for(int l = k + 1; l < m - 1; l++) {
					mk = min(mk, bad[i - 1][l][3]);
					ml = max(ml, bad[j + 1][l][2]);
					int mj = mn[l + 1][i][j];
					if(mj >= k + 1 || mk <= j || ml >= i || mi  <= l)
						continue;
					ans++;
				}
			}
		}
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:76:5: error: ambiguating new declaration of 'int count_rectangles(std::vector<std::vector<int> >)'
 int count_rectangles(vector<vector <int> > b) {
     ^~~~~~~~~~~~~~~~
In file included from rect.cpp:2:0:
rect.h:7:11: note: old declaration 'long long int count_rectangles(std::vector<std::vector<int> >)'
 long long count_rectangles(std::vector<std::vector<int> > a);
           ^~~~~~~~~~~~~~~~
rect.cpp:93:13: warning: overflow in implicit constant conversion [-Woverflow]
    int mi = OO;
             ^~
rect.cpp:96:14: warning: overflow in implicit constant conversion [-Woverflow]
     int mk = OO, ml = 0; 
              ^~