oj.uz

Submission #244952

# Submission time Handle Problem Language Result Execution time Memory
244952 2020-07-05T10:01:23 Z crossing0ver Rectangles (IOI19_rect) C++17
50 / 100
 3268 ms 208888 KB 
#include<bits/stdc++.h>
#define ll long long 
#ifndef local
#include "rect.h"
#endif
using namespace std;
int L[2505][2505][2],R[2505][2505][2],n,m;
ll sum[2505][2505];
void clearStack(stack<int>& s) {
	while(!s.empty()) s.pop();
}
void precalculate(vector<vector<int> > &a) {
	for (int i = 0; i < n; i++) {
		stack<int> s;
		for (int j = 0; j < m; j++) {
			int val = a[i][j];
			sum[i][j] = (j ? sum[i][j-1] : 0) + (i ? sum[i-1][j] : 0) - ( i && j ? sum[i-1][j-1]: 0) + a[i][j];
			while(!s.empty() && a[i][s.top()] < val)
				s.pop();
			L[i][j][0] = (s.empty() ? 0 : s.top() + 1);
			s.push(j);
		}
		clearStack(s);
		for (int j = m-1; j > -1; j--) {
			int val = a[i][j];
			while(!s.empty() && a[i][s.top()] < val)
				s.pop();
			R[i][j][0] = (s.empty() ? m-1 : s.top() - 1);
			s.push(j);
		}																		
	}
	for (int i = 0; i < m; i++) {
		stack<int> s;
		for (int j = 0; j < n; j++) {
			int val = a[j][i];
			while(!s.empty() && a[s.top()][i] < val)
				s.pop();
			L[j][i][1] = (s.empty() ? 0 : s.top() + 1);
			s.push(j);
		}
		clearStack(s);
		for (int j = n-1; j > -1; j--) {
			int val = a[j][i];
			while(!s.empty() && a[s.top()][i] < val)
				s.pop();
			R[j][i][1] = (s.empty() ? n-1 : s.top() - 1);
			s.push(j);
		}																		
	}
}
ll CaseSmall(vector<vector<int> > &a) {
	ll cnt = 0;
	for (int xi = 1; xi < m-1; xi++)
	 for (int xj = xi; xj < m-1; xj++) 
	 for (int yi = 1; yi < n-1; yi++)
	 for (int yj = yi; yj < n-1; yj++) {
	 	bool flag = 1;
	 	for (int k = xi; k <= xj && flag;k++) {
	 		if (R[yi-1][k][1] < yj) flag = 0;
	 		if (L[yj+1][k][1] > yi) flag = 0;
		}
		for (int k = yi; k <= yj && flag;k++) {
	 		if (R[k][xi-1][0] < xj) flag = 0;
	 		if (L[k][xj+1][0] > xi) flag = 0;
		 }
		 if (flag) cnt++;
	 }
	 return cnt;
}
ll SumRect(int xi,int xj,int yi,int yj) {
	return sum[yj][xj] + (yi && xi ? sum[yi-1][xi-1] : 0) -
	 (yi ? sum[yi-1][xj] : 0) -  (xi ? sum[yj][xi-1] : 0);	
}
ll CaseZero(vector<vector<int> > &a) {
	ll cnt = 0;
	for (int i = 0; i < n-1; i++)
	for (int j = 0; j < m-1; j++) {
		if (a[i][j+1]!= 1 || a[i+1][j] != 1) continue;
		int r = R[i+1][j][0];
		int d = R[i][j+1][1];
		r++;
		d++;
		if (r <= j+1 || d <= i+1 || r == m || d == n) continue;
		int x = SumRect(j,r,i,d);
		cnt += (SumRect(j+1,r - 1,i+1,d-1) == 0
		&& x == (2*(r - i + d - j)
		- (1 - a[i][j]) -(1 - a[i][r]) - (1-a[d][j]) - (1 - a[d][r])));
	}
	return cnt;
	
}
ll count_rectangles(vector<vector<int> > a) {
	 n = a.size();
	 m = a[0].size();
	 precalculate(a);
	 bool flag = 1;
	 for (int i = 0; i < n;i++)
	 for (int j = 0; j < m;j++)
	 	if (a[i][j] > 1) flag = 0;
	if (flag) return CaseZero(a);
	 ll cnt = 0; 
	 if (n <= 200 || m <= 200) return CaseSmall(a);
	/* for (int i = 0; i < n; i++)
	 for (int j = 0;j < m; j++) {
			cout << i <<' '<<j << ":\t" << "left " << L[i][j][0] <<" right "<< R[i][j][0] <<" up " << L[i][j][1] <<" down " << R[i][j][1] <<'\n';
	 }*/
	 return 0;
	 
}
#ifdef local
main() {
	cin >> n >> m;
	vector<vector<int> > a(n,vector<int>(m));
	for (int i = 0;i < n; i++ )
	for (int j = 0; j < m; j++)
		cin >> a[i][j];
	cout << count_rectangles(a);
	/*
6 5
4 8 7 5 6 
7 4 10 3 5 
9 7 20 14 2 
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
*/
/*
 4 4 
 1 1 1 1
 1 0 0 1
 1 1 1 1
 1 1 1 1*/
}
#endif

Compilation message

rect.cpp: In function 'long long int CaseSmall(std::vector<std::vector<int> >&)':
rect.cpp:53:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (int xi = 1; xi < m-1; xi++)
  ^~~
rect.cpp:68:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   return cnt;
   ^~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:101:6: warning: unused variable 'cnt' [-Wunused-variable]
   ll cnt = 0; 
      ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 6 ms 640 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 6 ms 640 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 5 ms 768 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 256 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 640 KB Output is correct
20 Correct 5 ms 640 KB Output is correct
21 Correct 5 ms 512 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 6 ms 640 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 6 ms 640 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 5 ms 768 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 256 KB Output is correct
17 Correct 40 ms 1536 KB Output is correct
18 Correct 28 ms 1536 KB Output is correct
19 Correct 28 ms 1536 KB Output is correct
20 Correct 20 ms 1664 KB Output is correct
21 Correct 23 ms 1536 KB Output is correct
22 Correct 32 ms 1536 KB Output is correct
23 Correct 24 ms 1536 KB Output is correct
24 Correct 11 ms 1408 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 640 KB Output is correct
28 Correct 5 ms 640 KB Output is correct
29 Correct 5 ms 512 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 6 ms 640 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 6 ms 640 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 5 ms 768 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 256 KB Output is correct
17 Correct 40 ms 1536 KB Output is correct
18 Correct 28 ms 1536 KB Output is correct
19 Correct 28 ms 1536 KB Output is correct
20 Correct 20 ms 1664 KB Output is correct
21 Correct 23 ms 1536 KB Output is correct
22 Correct 32 ms 1536 KB Output is correct
23 Correct 24 ms 1536 KB Output is correct
24 Correct 11 ms 1408 KB Output is correct
25 Correct 853 ms 4088 KB Output is correct
26 Correct 873 ms 4088 KB Output is correct
27 Correct 878 ms 4088 KB Output is correct
28 Correct 528 ms 4096 KB Output is correct
29 Correct 641 ms 4088 KB Output is correct
30 Correct 642 ms 4088 KB Output is correct
31 Correct 646 ms 4088 KB Output is correct
32 Correct 674 ms 4088 KB Output is correct
33 Correct 5 ms 384 KB Output is correct
34 Correct 5 ms 384 KB Output is correct
35 Correct 5 ms 640 KB Output is correct
36 Correct 5 ms 640 KB Output is correct
37 Correct 5 ms 512 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 6 ms 640 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 6 ms 640 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 5 ms 768 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 256 KB Output is correct
17 Correct 40 ms 1536 KB Output is correct
18 Correct 28 ms 1536 KB Output is correct
19 Correct 28 ms 1536 KB Output is correct
20 Correct 20 ms 1664 KB Output is correct
21 Correct 23 ms 1536 KB Output is correct
22 Correct 32 ms 1536 KB Output is correct
23 Correct 24 ms 1536 KB Output is correct
24 Correct 11 ms 1408 KB Output is correct
25 Correct 853 ms 4088 KB Output is correct
26 Correct 873 ms 4088 KB Output is correct
27 Correct 878 ms 4088 KB Output is correct
28 Correct 528 ms 4096 KB Output is correct
29 Correct 641 ms 4088 KB Output is correct
30 Correct 642 ms 4088 KB Output is correct
31 Correct 646 ms 4088 KB Output is correct
32 Correct 674 ms 4088 KB Output is correct
33 Incorrect 56 ms 24192 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3268 ms 632 KB Output is correct
2 Correct 1989 ms 604 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 19 ms 512 KB Output is correct
6 Correct 19 ms 512 KB Output is correct
7 Correct 19 ms 512 KB Output is correct
8 Correct 22 ms 512 KB Output is correct
9 Correct 19 ms 640 KB Output is correct
10 Correct 14 ms 384 KB Output is correct
11 Correct 16 ms 512 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 337 ms 95456 KB Output is correct
3 Correct 717 ms 207736 KB Output is correct
4 Correct 769 ms 208888 KB Output is correct
5 Correct 754 ms 208776 KB Output is correct
6 Correct 303 ms 103264 KB Output is correct
7 Correct 580 ms 205024 KB Output is correct
8 Correct 650 ms 208888 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 5 ms 640 KB Output is correct
13 Correct 5 ms 512 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 6 ms 640 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 6 ms 640 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 5 ms 768 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 256 KB Output is correct
17 Correct 40 ms 1536 KB Output is correct
18 Correct 28 ms 1536 KB Output is correct
19 Correct 28 ms 1536 KB Output is correct
20 Correct 20 ms 1664 KB Output is correct
21 Correct 23 ms 1536 KB Output is correct
22 Correct 32 ms 1536 KB Output is correct
23 Correct 24 ms 1536 KB Output is correct
24 Correct 11 ms 1408 KB Output is correct
25 Correct 853 ms 4088 KB Output is correct
26 Correct 873 ms 4088 KB Output is correct
27 Correct 878 ms 4088 KB Output is correct
28 Correct 528 ms 4096 KB Output is correct
29 Correct 641 ms 4088 KB Output is correct
30 Correct 642 ms 4088 KB Output is correct
31 Correct 646 ms 4088 KB Output is correct
32 Correct 674 ms 4088 KB Output is correct
33 Incorrect 56 ms 24192 KB Output isn't correct
34 Halted 0 ms 0 KB -