Submission #169844

#	Time	Username	Problem	Language	Result	Execution time	Memory
169844		arthur_nascimento	Rectangles (IOI19_rect)	C++14	72 / 100	5076 ms	809864 KiB

rect

#include "rect.h"
    #include <bits/stdc++.h>
    using namespace std;
    #define pb push_back
    #define debug 
    #define ll long long
    #define maxn 2505
     
     
    int lg[maxn];
     
    struct rmq {
    	
    	int len;
    	int arr[maxn];
    	short id[13][maxn];
    	inline int mx(int i,int j){
		return arr[id[i][j]];
		}
		int l,A,B;
    	
    	
    	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];
				}
			}
	}
	
	inline int pos(int x,int y){
		 l = lg[y-x+1];
		 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];
	}
	inline int val(int x,int y){
		 l = lg[y-x+1];
		 A = mx(l,x), B = mx(l,y-(1<<l)+1);
		return max(A,B);
	}
     
    }
     
    RMQ[4][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;
    }
     
    inline 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;
    		
    		
    		// min
    	if( -RMQ[2][yi-1].val(xi,xf) <= yf) return 0;
    	
    	
    	if(RMQ[3][yf+1].val(xi,xf) >= yi) return 0;
    		
    	//for(int j=yi;j<=yf;j++)
    	//	if( RMQ[1][j].val(xi,xf) >= min( M[xi-1][j],M[xf+1][j])) return 0;
    		
    	return 1;
     
    	//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);
     
    	if(RMQ[1][ym].val(xi,xf) >= min(M[xi-1][ym],M[xf+1][ym])) return 0;
    	
    	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++){
		
		stack<int> S;
		for(int j=m-1;j>=0;j--){
			while(S.size() > 0 && M[i][j] > M[i][S.top()]  ) S.pop();
			if(S.size() == 0) RMQ[2][j].arr[i] = m+1;
			else RMQ[2][j].arr[i] = S.top();
			S.push(j);
		}
	
		while(S.size() > 0) S.pop();
		
		
		for(int j=0;j<m;j++){
			while(S.size() > 0 && M[i][j] > M[i][S.top()] ) S.pop();
			if(S.size() == 0) RMQ[3][j].arr[i] = -1;
			else RMQ[3][j].arr[i] = S.top();
			S.push(j);
		}
		
		
	
	}
	
	for(int i=0;i<m;i++){
		RMQ[2][i].len = n;
		RMQ[3][i].len = n;
		for(int j=0;j<n;j++)
			RMQ[2][i].arr[j] *= -1;
		RMQ[2][i].build();
		RMQ[3][i].build();
	}
			
	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:107:40: 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:107:43: 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:107:46: 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:107:49: 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:115:20: warning: statement has no effect [-Wunused-value]
      debug("oi4\n");
                    ^
rect.cpp:129:24: warning: statement has no effect [-Wunused-value]
      debug("tchau 4\n");
                        ^
rect.cpp:118:10: 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:141:52: 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:141:55: 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:141:58: 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:141:61: 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:148:22: warning: left operand of comma operator has no effect [-Wunused-value]
       debug("A %d\n",A);
                      ^
rect.cpp:167:55: 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:167:58: 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:167:61: 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:167:64: 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:167:67: 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:167:69: 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:178:36: 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:178:39: 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:178:42: 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:178:45: 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:180:10: warning: unused variable 'mx' [-Wunused-variable]
      int mx = -1, id = -1;
          ^~
rect.cpp: In function 'long long int go(int, int)':
rect.cpp:203:19: warning: statement has no effect [-Wunused-value]
      debug("oi\n");
                   ^

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