oj.uz

Submission #169842

# Submission time Handle Problem Language Result Execution time Memory
169842 2019-12-23T00:36:36 Z arthur_nascimento Rectangles (IOI19_rect) C++14
50 / 100
 5000 ms 809692 KB 
#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]];
		}
    	
    	
    	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[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;
    }
     
    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

rect.cpp: In function 'int check(int, int, int, int)':
rect.cpp:106: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:106: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:106: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:106: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:114:20: warning: statement has no effect [-Wunused-value]
      debug("oi4\n");
                    ^
rect.cpp:128:24: warning: statement has no effect [-Wunused-value]
      debug("tchau 4\n");
                        ^
rect.cpp:117: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:140: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:140: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:140: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:140: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:147:22: warning: left operand of comma operator has no effect [-Wunused-value]
       debug("A %d\n",A);
                      ^
rect.cpp:166: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:166: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:166: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:166: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:166: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:166: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:177: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:177: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:177: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:177: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:179:10: warning: unused variable 'mx' [-Wunused-variable]
      int mx = -1, id = -1;
          ^~
rect.cpp: In function 'long long int go(int, int)':
rect.cpp:202:19: warning: statement has no effect [-Wunused-value]
      debug("oi\n");
                   ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 7 ms 7288 KB Output is correct
3 Correct 7 ms 7288 KB Output is correct
4 Correct 7 ms 7288 KB Output is correct
5 Correct 7 ms 7288 KB Output is correct
6 Correct 7 ms 7416 KB Output is correct
7 Correct 5 ms 4344 KB Output is correct
8 Correct 6 ms 6136 KB Output is correct
9 Correct 7 ms 7288 KB Output is correct
10 Correct 7 ms 7288 KB Output is correct
11 Correct 7 ms 7260 KB Output is correct
12 Correct 7 ms 7288 KB Output is correct
13 Correct 2 ms 632 KB Output is correct
14 Correct 3 ms 1272 KB Output is correct
15 Correct 4 ms 2424 KB Output is correct
16 Correct 3 ms 1016 KB Output is correct
17 Correct 2 ms 632 KB Output is correct
18 Correct 3 ms 1272 KB Output is correct
19 Correct 8 ms 7288 KB Output is correct
20 Correct 5 ms 4728 KB Output is correct
21 Correct 3 ms 1276 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 7 ms 7288 KB Output is correct
3 Correct 7 ms 7288 KB Output is correct
4 Correct 7 ms 7288 KB Output is correct
5 Correct 7 ms 7288 KB Output is correct
6 Correct 7 ms 7416 KB Output is correct
7 Correct 5 ms 4344 KB Output is correct
8 Correct 6 ms 6136 KB Output is correct
9 Correct 7 ms 7288 KB Output is correct
10 Correct 7 ms 7288 KB Output is correct
11 Correct 7 ms 7260 KB Output is correct
12 Correct 7 ms 7288 KB Output is correct
13 Correct 2 ms 632 KB Output is correct
14 Correct 3 ms 1272 KB Output is correct
15 Correct 4 ms 2424 KB Output is correct
16 Correct 3 ms 1016 KB Output is correct
17 Correct 20 ms 19448 KB Output is correct
18 Correct 23 ms 19448 KB Output is correct
19 Correct 22 ms 19448 KB Output is correct
20 Correct 18 ms 19452 KB Output is correct
21 Correct 21 ms 19448 KB Output is correct
22 Correct 18 ms 19192 KB Output is correct
23 Correct 18 ms 19448 KB Output is correct
24 Correct 12 ms 12280 KB Output is correct
25 Correct 2 ms 632 KB Output is correct
26 Correct 3 ms 1272 KB Output is correct
27 Correct 8 ms 7288 KB Output is correct
28 Correct 5 ms 4728 KB Output is correct
29 Correct 3 ms 1276 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 7 ms 7288 KB Output is correct
3 Correct 7 ms 7288 KB Output is correct
4 Correct 7 ms 7288 KB Output is correct
5 Correct 7 ms 7288 KB Output is correct
6 Correct 7 ms 7416 KB Output is correct
7 Correct 5 ms 4344 KB Output is correct
8 Correct 6 ms 6136 KB Output is correct
9 Correct 7 ms 7288 KB Output is correct
10 Correct 7 ms 7288 KB Output is correct
11 Correct 7 ms 7260 KB Output is correct
12 Correct 7 ms 7288 KB Output is correct
13 Correct 2 ms 632 KB Output is correct
14 Correct 3 ms 1272 KB Output is correct
15 Correct 4 ms 2424 KB Output is correct
16 Correct 3 ms 1016 KB Output is correct
17 Correct 20 ms 19448 KB Output is correct
18 Correct 23 ms 19448 KB Output is correct
19 Correct 22 ms 19448 KB Output is correct
20 Correct 18 ms 19452 KB Output is correct
21 Correct 21 ms 19448 KB Output is correct
22 Correct 18 ms 19192 KB Output is correct
23 Correct 18 ms 19448 KB Output is correct
24 Correct 12 ms 12280 KB Output is correct
25 Correct 105 ms 51212 KB Output is correct
26 Correct 104 ms 51236 KB Output is correct
27 Correct 112 ms 51224 KB Output is correct
28 Correct 58 ms 51192 KB Output is correct
29 Correct 54 ms 51192 KB Output is correct
30 Correct 55 ms 51192 KB Output is correct
31 Correct 63 ms 51192 KB Output is correct
32 Correct 54 ms 50652 KB Output is correct
33 Correct 2 ms 632 KB Output is correct
34 Correct 3 ms 1272 KB Output is correct
35 Correct 8 ms 7288 KB Output is correct
36 Correct 5 ms 4728 KB Output is correct
37 Correct 3 ms 1276 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 7 ms 7288 KB Output is correct
3 Correct 7 ms 7288 KB Output is correct
4 Correct 7 ms 7288 KB Output is correct
5 Correct 7 ms 7288 KB Output is correct
6 Correct 7 ms 7416 KB Output is correct
7 Correct 5 ms 4344 KB Output is correct
8 Correct 6 ms 6136 KB Output is correct
9 Correct 7 ms 7288 KB Output is correct
10 Correct 7 ms 7288 KB Output is correct
11 Correct 7 ms 7260 KB Output is correct
12 Correct 7 ms 7288 KB Output is correct
13 Correct 2 ms 632 KB Output is correct
14 Correct 3 ms 1272 KB Output is correct
15 Correct 4 ms 2424 KB Output is correct
16 Correct 3 ms 1016 KB Output is correct
17 Correct 20 ms 19448 KB Output is correct
18 Correct 23 ms 19448 KB Output is correct
19 Correct 22 ms 19448 KB Output is correct
20 Correct 18 ms 19452 KB Output is correct
21 Correct 21 ms 19448 KB Output is correct
22 Correct 18 ms 19192 KB Output is correct
23 Correct 18 ms 19448 KB Output is correct
24 Correct 12 ms 12280 KB Output is correct
25 Correct 105 ms 51212 KB Output is correct
26 Correct 104 ms 51236 KB Output is correct
27 Correct 112 ms 51224 KB Output is correct
28 Correct 58 ms 51192 KB Output is correct
29 Correct 54 ms 51192 KB Output is correct
30 Correct 55 ms 51192 KB Output is correct
31 Correct 63 ms 51192 KB Output is correct
32 Correct 54 ms 50652 KB Output is correct
33 Correct 330 ms 206496 KB Output is correct
34 Correct 338 ms 206376 KB Output is correct
35 Correct 341 ms 206460 KB Output is correct
36 Correct 358 ms 206432 KB Output is correct
37 Execution timed out 5108 ms 206328 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 422256 KB Output is correct
2 Correct 322 ms 358616 KB Output is correct
3 Correct 374 ms 422272 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 364 ms 422276 KB Output is correct
6 Correct 387 ms 422208 KB Output is correct
7 Correct 372 ms 422392 KB Output is correct
8 Correct 388 ms 422388 KB Output is correct
9 Correct 375 ms 422392 KB Output is correct
10 Correct 364 ms 421716 KB Output is correct
11 Correct 371 ms 421876 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 1398 ms 631300 KB Output is correct
3 Correct 2565 ms 808412 KB Output is correct
4 Correct 2701 ms 809336 KB Output is correct
5 Correct 2598 ms 809596 KB Output is correct
6 Correct 1237 ms 671864 KB Output is correct
7 Correct 2079 ms 772408 KB Output is correct
8 Correct 2236 ms 809692 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 3 ms 1272 KB Output is correct
11 Correct 8 ms 7288 KB Output is correct
12 Correct 5 ms 4728 KB Output is correct
13 Correct 3 ms 1276 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 7 ms 7288 KB Output is correct
3 Correct 7 ms 7288 KB Output is correct
4 Correct 7 ms 7288 KB Output is correct
5 Correct 7 ms 7288 KB Output is correct
6 Correct 7 ms 7416 KB Output is correct
7 Correct 5 ms 4344 KB Output is correct
8 Correct 6 ms 6136 KB Output is correct
9 Correct 7 ms 7288 KB Output is correct
10 Correct 7 ms 7288 KB Output is correct
11 Correct 7 ms 7260 KB Output is correct
12 Correct 7 ms 7288 KB Output is correct
13 Correct 2 ms 632 KB Output is correct
14 Correct 3 ms 1272 KB Output is correct
15 Correct 4 ms 2424 KB Output is correct
16 Correct 3 ms 1016 KB Output is correct
17 Correct 20 ms 19448 KB Output is correct
18 Correct 23 ms 19448 KB Output is correct
19 Correct 22 ms 19448 KB Output is correct
20 Correct 18 ms 19452 KB Output is correct
21 Correct 21 ms 19448 KB Output is correct
22 Correct 18 ms 19192 KB Output is correct
23 Correct 18 ms 19448 KB Output is correct
24 Correct 12 ms 12280 KB Output is correct
25 Correct 105 ms 51212 KB Output is correct
26 Correct 104 ms 51236 KB Output is correct
27 Correct 112 ms 51224 KB Output is correct
28 Correct 58 ms 51192 KB Output is correct
29 Correct 54 ms 51192 KB Output is correct
30 Correct 55 ms 51192 KB Output is correct
31 Correct 63 ms 51192 KB Output is correct
32 Correct 54 ms 50652 KB Output is correct
33 Correct 330 ms 206496 KB Output is correct
34 Correct 338 ms 206376 KB Output is correct
35 Correct 341 ms 206460 KB Output is correct
36 Correct 358 ms 206432 KB Output is correct
37 Execution timed out 5108 ms 206328 KB Time limit exceeded
38 Halted 0 ms 0 KB -