Submission #169810

#	Time	Username	Problem	Language	Result	Execution time	Memory
169810		arthur_nascimento	Rectangles (IOI19_rect)	C++14	37 / 100	5034 ms	1048580 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define debug 
#define ll long long
#define maxn 2525


int lg[maxn];

struct rmq {
	
	int len;
	int arr[maxn];
	int mx[13][maxn];
	int id[13][maxn];
	
	void build(){
		lg[1] = 0;
		for(int i=2;i<=len;i++)
			lg[i] = lg[i-1] + (i == (i&-i));
	
		for(int i=0;i<len;i++){
			mx[0][i] = arr[i];
			id[0][i] = i;
		}
		for(int i=1;i<13;i++)
			for(int j=0;j<len;j++){
				int ot = min(len-1, j + ( 1 << (i-1)));
				int A = mx[i-1][j], B = mx[i-1][ot];
				if(A > B){
					mx[i][j] = A;
					id[i][j] = id[i-1][j];
				}
				else {
					mx[i][j] = B;
					id[i][j] = id[i-1][ot];
				}
			}
	}
	
	int pos(int x,int y){
		int l = lg[y-x+1];
		int A = mx[l][x], B = mx[l][y-(1<<l)+1];
		if(A > B) return id[l][x];
		else return id[l][y-(1<<l)+1];
	}
	int val(int x,int y){
		int l = lg[y-x+1];
		int A = mx[l][x], B = mx[l][y-(1<<l)+1];
		return max(A,B);
	}

}

RMQ[2][maxn];


int M[maxn][maxn];

int n,m;

int line(int i,int yi,int yf){
	int r = 1;
	for(int j=yi;j<=yf;j++)
		if(M[i][j] >= M[i][yi-1] || M[i][j] >= M[i][yf+1]) r = 0;
	return r;
}

int column(int j,int xi,int xf){
	int r = 1;
	for(int i=xi;i<=xf;i++)
		if(M[i][j] >= M[xi-1][j] || M[i][j] >= M[xf+1][j]) r = 0;
	return r;
}

int check(int xi,int xf,int yi,int yf){

	for(int i=xi;i<=xf;i++)
		if( RMQ[0][i].val(yi,yf) >= min( M[i][yi-1],M[i][yf+1])) return 0;

	//return 1;
	int r = 1;
	assert(xi >= 1 && xf <= n-2 && yi >= 1 && yf <= m-2);
	//for(int i=xi;i<=xf;i++)
	//	r *= line(i,yi,yf);
	for(int j=yi;j<=yf;j++)
		r *= column(j,xi,xf);
	if(r)
		debug("achou x:%d~%d y: %d~%d\n",xi,xf,yi,yf);
	return r;
} 

ll go4(int xi,int xf,int yi,int yf,int ym){

	if(xi > xf || yi > yf) return 0;
	if(yi > ym || yf < ym) return 0;
	debug("oi4\n");
	ll ans = check(xi,xf,yi,yf);
	
	int mx = -1, id = -1;
	
	/*for(int i=yi;i<=yf;i++)
		if(M[xi][i] > mx){
			mx = M[xi][i];
			id = i;
		}*/
		
	id = RMQ[0][xi].pos(yi,yf);
		
	ans += go4(xi,xf,yi,id-1,ym) + go4(xi,xf,id+1,yf,ym);
	debug("tchau 4\n");
	return ans;

}

ll go3(int xi,int xf,int yi,int yf,int ym){

	if(xi == 0 || xf == n-1) return 0;
	if(xi > xf) return 0;
	
	int A = ym, B = ym;
	
	debug("oi x: %d~%d y: %d~%d quebra A ? B ?\n",xi,xf,yi,yf);

	
	while(1){
		A--;
		if(A == 0 || A < yi) break;
		debug("A %d\n",A);
		int ok = 1;
		//for(int i=xi;i<=xf;i++)
		//	if(M[i][A] >= M[xi-1][A] || M[i][A] >= M[xf+1][A]) ok = 0;
		if(RMQ[1][A].val(xi,xf) >= min(M[xi-1][A],M[xf+1][A])) ok = 0;
		if(ok == 0) break;
	}
	A++;
	
	while(1){
		B++;
		if(B == m-1 || B > yf) break;
		int ok = 1;
		for(int i=xi;i<=xf;i++)
			if(M[i][B] >= M[xi-1][B] || M[i][B] >= M[xf+1][B]) ok = 0;
		if(ok == 0) break;
	}
	B--;
	
	debug("go3 x: %d~%d y: %d~%d quebra A %d B %d\n",xi,xf,yi,yf,A,B);
	
	return go4(xi,xf,A,B,ym);

}

ll go2(int xi,int xf,int yi,int yf,int ym){
	
	if(xi > xf) return 0;
	if(yi > yf) return 0;
	if(ym == 0 || ym == m-1) return 0;
	debug("go2 x %d~%d y %d~%d\n",xi,xf,yi,yf);
	
	int mx = -1, id = -1;
	
	/*for(int i=xi;i<=xf;i++)
		if(M[i][ym] > mx){
			mx = M[i][ym];
			id = i;
		}*/
	
	
	id = RMQ[1][ym].pos(xi,xf);
	
		
	ll ans = go3(xi,id-1,yi,yf,ym) + go3(id+1,xf,yi,yf,ym) + go2(xi,id-1,yi,yf,ym) + go2(id+1,xf,yi,yf,ym);
	
	return ans;

}

ll go(int yi,int yf){

	if(yi > yf) return 0;
	
	int ym = (yi+yf)/2;
	debug("oi\n");
	
	ll ans = go(yi,ym-1) + go(ym+1,yf) + go2(0,n-1,yi,yf,ym);
	
	return ans;

}

long long count_rectangles(std::vector<std::vector<int> > a) {
	
	 n = a.size();
	 m = a[0].size();
	
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			M[i][j] = a[i][j];
			
	for(int i=0;i<n;i++){
		
		RMQ[0][i].len = m;
		
		for(int j=0;j<m;j++)
			RMQ[0][i].arr[j] = M[i][j];
			
		RMQ[0][i].build();
	
	}	
	
	for(int j=0;j<m;j++){
	
		RMQ[1][j].len = n;
		for(int i=0;i<n;i++)
			RMQ[1][j].arr[i] = M[i][j];
			
		RMQ[1][j].build();
	
	}	
	
	return go(0,m-1);
	
}

Compilation message (stderr)

rect.cpp: In function 'int check(int, int, int, int)':
rect.cpp:91:36: warning: left operand of comma operator has no effect [-Wunused-value]
   debug("achou x:%d~%d y: %d~%d\n",xi,xf,yi,yf);
                                    ^~
rect.cpp:91:39: warning: right operand of comma operator has no effect [-Wunused-value]
   debug("achou x:%d~%d y: %d~%d\n",xi,xf,yi,yf);
                                       ^~
rect.cpp:91:42: warning: right operand of comma operator has no effect [-Wunused-value]
   debug("achou x:%d~%d y: %d~%d\n",xi,xf,yi,yf);
                                          ^~
rect.cpp:91:45: warning: right operand of comma operator has no effect [-Wunused-value]
   debug("achou x:%d~%d y: %d~%d\n",xi,xf,yi,yf);
                                             ^~
rect.cpp: In function 'long long int go4(int, int, int, int, int)':
rect.cpp:99:16: warning: statement has no effect [-Wunused-value]
  debug("oi4\n");
                ^
rect.cpp:113:20: warning: statement has no effect [-Wunused-value]
  debug("tchau 4\n");
                    ^
rect.cpp:102:6: warning: unused variable 'mx' [-Wunused-variable]
  int mx = -1, id = -1;
      ^~
rect.cpp: In function 'long long int go3(int, int, int, int, int)':
rect.cpp:125:48: warning: left operand of comma operator has no effect [-Wunused-value]
  debug("oi x: %d~%d y: %d~%d quebra A ? B ?\n",xi,xf,yi,yf);
                                                ^~
rect.cpp:125:51: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("oi x: %d~%d y: %d~%d quebra A ? B ?\n",xi,xf,yi,yf);
                                                   ^~
rect.cpp:125:54: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("oi x: %d~%d y: %d~%d quebra A ? B ?\n",xi,xf,yi,yf);
                                                      ^~
rect.cpp:125:57: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("oi x: %d~%d y: %d~%d quebra A ? B ?\n",xi,xf,yi,yf);
                                                         ^~
rect.cpp:131:18: warning: left operand of comma operator has no effect [-Wunused-value]
   debug("A %d\n",A);
                  ^
rect.cpp:150:51: warning: left operand of comma operator has no effect [-Wunused-value]
  debug("go3 x: %d~%d y: %d~%d quebra A %d B %d\n",xi,xf,yi,yf,A,B);
                                                   ^~
rect.cpp:150:54: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("go3 x: %d~%d y: %d~%d quebra A %d B %d\n",xi,xf,yi,yf,A,B);
                                                      ^~
rect.cpp:150:57: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("go3 x: %d~%d y: %d~%d quebra A %d B %d\n",xi,xf,yi,yf,A,B);
                                                         ^~
rect.cpp:150:60: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("go3 x: %d~%d y: %d~%d quebra A %d B %d\n",xi,xf,yi,yf,A,B);
                                                            ^~
rect.cpp:150:63: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("go3 x: %d~%d y: %d~%d quebra A %d B %d\n",xi,xf,yi,yf,A,B);
                                                               ^
rect.cpp:150:65: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("go3 x: %d~%d y: %d~%d quebra A %d B %d\n",xi,xf,yi,yf,A,B);
                                                                 ^
rect.cpp: In function 'long long int go2(int, int, int, int, int)':
rect.cpp:161:32: warning: left operand of comma operator has no effect [-Wunused-value]
  debug("go2 x %d~%d y %d~%d\n",xi,xf,yi,yf);
                                ^~
rect.cpp:161:35: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("go2 x %d~%d y %d~%d\n",xi,xf,yi,yf);
                                   ^~
rect.cpp:161:38: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("go2 x %d~%d y %d~%d\n",xi,xf,yi,yf);
                                      ^~
rect.cpp:161:41: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("go2 x %d~%d y %d~%d\n",xi,xf,yi,yf);
                                         ^~
rect.cpp:163:6: warning: unused variable 'mx' [-Wunused-variable]
  int mx = -1, id = -1;
      ^~
rect.cpp: In function 'long long int go(int, int)':
rect.cpp:186:15: warning: statement has no effect [-Wunused-value]
  debug("oi\n");
               ^

• 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