oj.uz

Submission #400792

# Submission time Handle Problem Language Result Execution time Memory
400792 2021-05-08T16:38:50 Z mosiashvililuka Rectangles (IOI19_rect) C++17
100 / 100
 1883 ms 220116 KB 
#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[2509][2509],pas;
short lf[2509][2509],rg[2509][2509],zm[2509][2509],qv[2509][2509];
short ZM[2509][2509],RG[2509][2509],QV[2509][2509],LF[2509][2509];
stack <int> st;
void chk(int q, int w, int qq, int ww){
	if(q>qq||w>ww) return;
	if(q<=1||w<=1||qq>=a||ww>=b) return;
	if(rg[q][w-1]==ww+1){
		if(RG[q][w-1]<qq){
			return;
		}
	}else{
		if(lf[q][ww+1]==w-1){
			if(LF[q][ww+1]<qq){
				return;
			}
		}else{
			return;
		}
	}
	if(zm[q-1][w]==qq+1){
		if(ZM[q-1][w]<ww){
			return;
		}
	}else{
		if(qv[qq+1][w]==q-1){
			if(QV[qq+1][w]<ww){
				return;
			}
		}else{
			return;
		}
	}
	pas++;
}
long long count_rectangles(std::vector<std::vector<int> > VA) {
	a=VA.size();
	b=VA[0].size();
	if(a<3||b<3){
		return 0;
	}
	for(i=1; i<=a; i++){
		for(j=1; j<=b; j++){
			f[i][j]=VA[i-1][j-1];
		}
	}
	for(i=1; i<=a; i++){
		while(st.size()) st.pop();
		for(j=1; j<=b; j++){
			while(st.size()&&f[i][st.top()]<f[i][j]){
				st.pop();
			}
			if(st.size()){
				lf[i][j]=st.top();
			}
			st.push(j);
		}
		while(st.size()) st.pop();
		for(j=b; j>=1; j--){
			while(st.size()&&f[i][st.top()]<f[i][j]){
				st.pop();
			}
			if(st.size()){
				if(f[i][st.top()]!=f[i][j]) rg[i][j]=st.top();
			}
			st.push(j);
		}
	}
	for(j=1; j<=b; j++){
		while(st.size()) st.pop();
		for(i=1; i<=a; i++){
			while(st.size()&&f[st.top()][j]<f[i][j]){
				st.pop();
			}
			if(st.size()){
				qv[i][j]=st.top();
			}
			st.push(i);
		}
		while(st.size()) st.pop();
		for(i=a; i>=1; i--){
			while(st.size()&&f[st.top()][j]<f[i][j]){
				st.pop();
			}
			if(st.size()){
				if(f[st.top()][j]!=f[i][j]) zm[i][j]=st.top();
			}
			st.push(i);
		}
	}
	for(j=b; j>=1; j--){
		for(i=1; i<=a; i++){
			if(qv[i][j]!=0){
				if(qv[i][j+1]==qv[i][j]){
					QV[i][j]=QV[i][j+1];
				}else{
					if(zm[qv[i][j]][j+1]==i){
						QV[i][j]=ZM[qv[i][j]][j+1];
					}else{
						QV[i][j]=j;
					}
				}
			}
			if(zm[i][j]!=0){
				if(zm[i][j+1]==zm[i][j]){
					ZM[i][j]=ZM[i][j+1];
				}else{
					if(qv[zm[i][j]][j+1]==i){
						ZM[i][j]=QV[zm[i][j]][j+1];
					}else{
						ZM[i][j]=j;
					}
				}
			}
		}
	}
	for(i=a; i>=1; i--){
		for(j=1; j<=b; j++){
			if(lf[i][j]!=0){
				if(lf[i+1][j]==lf[i][j]){
					LF[i][j]=LF[i+1][j];
				}else{
					if(rg[i+1][lf[i][j]]==j){
						LF[i][j]=RG[i+1][lf[i][j]];
					}else{
						LF[i][j]=i;
					}
				}
			}
			if(rg[i][j]!=0){
				if(rg[i+1][j]==rg[i][j]){
					RG[i][j]=RG[i+1][j];
				}else{
					if(lf[i+1][rg[i][j]]==j){
						RG[i][j]=LF[i+1][rg[i][j]];
					}else{
						RG[i][j]=i;
					}
				}
			}
		}
	}
	for(i=2; i<a; i++){
		for(j=2; j<b; j++){
			if(zm[i-1][j]!=0&&rg[i][j-1]!=0){
				chk(i,j,zm[i-1][j]-1,rg[i][j-1]-1);
			}
			if(qv[i+1][j]!=0&&rg[i][j-1]!=0){
				chk(qv[i+1][j]+1,j,i,rg[i][j-1]-1);
			}
			if(rg[i][j-1]!=0){
			jj=rg[i][j-1]-1;
			if(zm[i-1][jj]!=0){
				chk(i,j,zm[i-1][jj]-1,jj);
			}
			if(qv[i+1][jj]!=0){
				chk(qv[i+1][jj]+1,j,i,jj);
			}
			}
			if(zm[i-1][j]!=0&&lf[i][j+1]!=0){
				chk(i,lf[i][j+1]+1,zm[i-1][j]-1,j);
			}
			if(qv[i+1][j]!=0&&lf[i][j+1]!=0){
				chk(qv[i+1][j]+1,lf[i][j+1]+1,i,j);
			}
			if(lf[i][j+1]!=0){
			jj=lf[i][j+1]+1;
			if(zm[i-1][jj]!=0){
				chk(i,jj,zm[i-1][jj]-1,j);
			}
			if(qv[i+1][jj]!=0){
				chk(qv[i+1][jj]+1,jj,i,j);
			}
			}
		}
	}
	pas/=2;
	return pas;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 1356 KB Output is correct
3 Correct 1 ms 1356 KB Output is correct
4 Correct 1 ms 1356 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 1356 KB Output is correct
7 Correct 1 ms 1356 KB Output is correct
8 Correct 1 ms 684 KB Output is correct
9 Correct 2 ms 1356 KB Output is correct
10 Correct 2 ms 1320 KB Output is correct
11 Correct 1 ms 1356 KB Output is correct
12 Correct 2 ms 1356 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 424 KB Output is correct
17 Correct 1 ms 300 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 1324 KB Output is correct
20 Correct 1 ms 1100 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 1356 KB Output is correct
3 Correct 1 ms 1356 KB Output is correct
4 Correct 1 ms 1356 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 1356 KB Output is correct
7 Correct 1 ms 1356 KB Output is correct
8 Correct 1 ms 684 KB Output is correct
9 Correct 2 ms 1356 KB Output is correct
10 Correct 2 ms 1320 KB Output is correct
11 Correct 1 ms 1356 KB Output is correct
12 Correct 2 ms 1356 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 424 KB Output is correct
17 Correct 1 ms 300 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 1324 KB Output is correct
20 Correct 1 ms 1100 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 3 ms 3404 KB Output is correct
23 Correct 3 ms 3312 KB Output is correct
24 Correct 3 ms 3404 KB Output is correct
25 Correct 3 ms 3404 KB Output is correct
26 Correct 4 ms 3276 KB Output is correct
27 Correct 4 ms 3404 KB Output is correct
28 Correct 4 ms 3276 KB Output is correct
29 Correct 3 ms 3276 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 1356 KB Output is correct
3 Correct 1 ms 1356 KB Output is correct
4 Correct 1 ms 1356 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 1356 KB Output is correct
7 Correct 1 ms 1356 KB Output is correct
8 Correct 1 ms 684 KB Output is correct
9 Correct 2 ms 1356 KB Output is correct
10 Correct 2 ms 1320 KB Output is correct
11 Correct 1 ms 1356 KB Output is correct
12 Correct 2 ms 1356 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 424 KB Output is correct
17 Correct 3 ms 3404 KB Output is correct
18 Correct 3 ms 3312 KB Output is correct
19 Correct 3 ms 3404 KB Output is correct
20 Correct 3 ms 3404 KB Output is correct
21 Correct 4 ms 3276 KB Output is correct
22 Correct 4 ms 3404 KB Output is correct
23 Correct 4 ms 3276 KB Output is correct
24 Correct 3 ms 3276 KB Output is correct
25 Correct 1 ms 300 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 1 ms 1324 KB Output is correct
28 Correct 1 ms 1100 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 10 ms 8892 KB Output is correct
31 Correct 10 ms 8780 KB Output is correct
32 Correct 10 ms 8908 KB Output is correct
33 Correct 11 ms 8652 KB Output is correct
34 Correct 13 ms 8780 KB Output is correct
35 Correct 13 ms 8908 KB Output is correct
36 Correct 13 ms 8896 KB Output is correct
37 Correct 13 ms 8780 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 1356 KB Output is correct
3 Correct 1 ms 1356 KB Output is correct
4 Correct 1 ms 1356 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 1356 KB Output is correct
7 Correct 1 ms 1356 KB Output is correct
8 Correct 1 ms 684 KB Output is correct
9 Correct 2 ms 1356 KB Output is correct
10 Correct 2 ms 1320 KB Output is correct
11 Correct 1 ms 1356 KB Output is correct
12 Correct 2 ms 1356 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 424 KB Output is correct
17 Correct 3 ms 3404 KB Output is correct
18 Correct 3 ms 3312 KB Output is correct
19 Correct 3 ms 3404 KB Output is correct
20 Correct 3 ms 3404 KB Output is correct
21 Correct 4 ms 3276 KB Output is correct
22 Correct 4 ms 3404 KB Output is correct
23 Correct 4 ms 3276 KB Output is correct
24 Correct 3 ms 3276 KB Output is correct
25 Correct 10 ms 8892 KB Output is correct
26 Correct 10 ms 8780 KB Output is correct
27 Correct 10 ms 8908 KB Output is correct
28 Correct 11 ms 8652 KB Output is correct
29 Correct 13 ms 8780 KB Output is correct
30 Correct 13 ms 8908 KB Output is correct
31 Correct 13 ms 8896 KB Output is correct
32 Correct 13 ms 8780 KB Output is correct
33 Correct 1 ms 300 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 1 ms 1324 KB Output is correct
36 Correct 1 ms 1100 KB Output is correct
37 Correct 1 ms 204 KB Output is correct
38 Correct 78 ms 36388 KB Output is correct
39 Correct 78 ms 36420 KB Output is correct
40 Correct 79 ms 36456 KB Output is correct
41 Correct 79 ms 36384 KB Output is correct
42 Correct 105 ms 37292 KB Output is correct
43 Correct 96 ms 37300 KB Output is correct
44 Correct 98 ms 37284 KB Output is correct
45 Correct 93 ms 34976 KB Output is correct
46 Correct 90 ms 37284 KB Output is correct
47 Correct 102 ms 37212 KB Output is correct
48 Correct 133 ms 37228 KB Output is correct
49 Correct 144 ms 37404 KB Output is correct
50 Correct 76 ms 33132 KB Output is correct
51 Correct 68 ms 19140 KB Output is correct
52 Correct 136 ms 37308 KB Output is correct
53 Correct 136 ms 37292 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 1 ms 444 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 564 KB Output is correct
9 Correct 2 ms 564 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 1324 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 502 ms 84376 KB Output is correct
8 Correct 1143 ms 172120 KB Output is correct
9 Correct 1141 ms 173132 KB Output is correct
10 Correct 1154 ms 172928 KB Output is correct
11 Correct 369 ms 61764 KB Output is correct
12 Correct 738 ms 120972 KB Output is correct
13 Correct 776 ms 123972 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 1356 KB Output is correct
3 Correct 1 ms 1356 KB Output is correct
4 Correct 1 ms 1356 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 1356 KB Output is correct
7 Correct 1 ms 1356 KB Output is correct
8 Correct 1 ms 684 KB Output is correct
9 Correct 2 ms 1356 KB Output is correct
10 Correct 2 ms 1320 KB Output is correct
11 Correct 1 ms 1356 KB Output is correct
12 Correct 2 ms 1356 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 424 KB Output is correct
17 Correct 3 ms 3404 KB Output is correct
18 Correct 3 ms 3312 KB Output is correct
19 Correct 3 ms 3404 KB Output is correct
20 Correct 3 ms 3404 KB Output is correct
21 Correct 4 ms 3276 KB Output is correct
22 Correct 4 ms 3404 KB Output is correct
23 Correct 4 ms 3276 KB Output is correct
24 Correct 3 ms 3276 KB Output is correct
25 Correct 10 ms 8892 KB Output is correct
26 Correct 10 ms 8780 KB Output is correct
27 Correct 10 ms 8908 KB Output is correct
28 Correct 11 ms 8652 KB Output is correct
29 Correct 13 ms 8780 KB Output is correct
30 Correct 13 ms 8908 KB Output is correct
31 Correct 13 ms 8896 KB Output is correct
32 Correct 13 ms 8780 KB Output is correct
33 Correct 78 ms 36388 KB Output is correct
34 Correct 78 ms 36420 KB Output is correct
35 Correct 79 ms 36456 KB Output is correct
36 Correct 79 ms 36384 KB Output is correct
37 Correct 105 ms 37292 KB Output is correct
38 Correct 96 ms 37300 KB Output is correct
39 Correct 98 ms 37284 KB Output is correct
40 Correct 93 ms 34976 KB Output is correct
41 Correct 90 ms 37284 KB Output is correct
42 Correct 102 ms 37212 KB Output is correct
43 Correct 133 ms 37228 KB Output is correct
44 Correct 144 ms 37404 KB Output is correct
45 Correct 76 ms 33132 KB Output is correct
46 Correct 68 ms 19140 KB Output is correct
47 Correct 136 ms 37308 KB Output is correct
48 Correct 136 ms 37292 KB Output is correct
49 Correct 2 ms 588 KB Output is correct
50 Correct 2 ms 588 KB Output is correct
51 Correct 1 ms 444 KB Output is correct
52 Correct 1 ms 204 KB Output is correct
53 Correct 2 ms 620 KB Output is correct
54 Correct 2 ms 588 KB Output is correct
55 Correct 2 ms 588 KB Output is correct
56 Correct 2 ms 564 KB Output is correct
57 Correct 2 ms 564 KB Output is correct
58 Correct 1 ms 332 KB Output is correct
59 Correct 1 ms 332 KB Output is correct
60 Correct 1 ms 588 KB Output is correct
61 Correct 502 ms 84376 KB Output is correct
62 Correct 1143 ms 172120 KB Output is correct
63 Correct 1141 ms 173132 KB Output is correct
64 Correct 1154 ms 172928 KB Output is correct
65 Correct 369 ms 61764 KB Output is correct
66 Correct 738 ms 120972 KB Output is correct
67 Correct 776 ms 123972 KB Output is correct
68 Correct 1 ms 300 KB Output is correct
69 Correct 1 ms 204 KB Output is correct
70 Correct 1 ms 1324 KB Output is correct
71 Correct 1 ms 1100 KB Output is correct
72 Correct 1 ms 204 KB Output is correct
73 Correct 1089 ms 171396 KB Output is correct
74 Correct 1083 ms 218180 KB Output is correct
75 Correct 1070 ms 171368 KB Output is correct
76 Correct 1079 ms 218044 KB Output is correct
77 Correct 1283 ms 172264 KB Output is correct
78 Correct 1020 ms 104416 KB Output is correct
79 Correct 1149 ms 176440 KB Output is correct
80 Correct 1734 ms 194948 KB Output is correct
81 Correct 1086 ms 103444 KB Output is correct
82 Correct 1491 ms 162404 KB Output is correct
83 Correct 1883 ms 172152 KB Output is correct
84 Correct 1148 ms 103520 KB Output is correct
85 Correct 1790 ms 172276 KB Output is correct
86 Correct 1757 ms 167592 KB Output is correct
87 Correct 865 ms 181360 KB Output is correct
88 Correct 1377 ms 219924 KB Output is correct
89 Correct 1451 ms 172280 KB Output is correct
90 Correct 1367 ms 220116 KB Output is correct