oj.uz

Submission #152084

# Submission time Handle Problem Language Result Execution time Memory
152084 2019-09-06T10:32:19 Z oolimry Rectangles (IOI19_rect) C++14
27 / 100
 5000 ms 47964 KB 
#include <bits/stdc++.h>
 
using namespace std;
 /*
class Segment{
public:
	vector<int> tree;
	int n;
	
	void create(int nn){
		n = nn;
		for(int i = 0;i < 2 * n + 5;i++){
			tree.push_back(-1);
		}
	}
	
	void update(int i, int x){
		i += n;
		while(i > 0){
			tree[i] = max(tree[i],x);
			i >>= 1;
		}
	}
	
	int query(int l, int r){
		int ans = -1;
		for(l += n,r += n;l < r;l >>= 1, r >>= 1){
			if(l&1){
				ans = max(ans,tree[l]);
				l++;
			}
			if(r&1){
				r--;
				ans = max(ans,tree[r]);
			}
		}
		return ans;
	}
};
*/
static int tree[1405][1405];
inline void update(int t, int i, int x){
	i += 700;
	while(i > 0){
		tree[t][i] = max(tree[t][i],x);
		i >>= 1;
	}
}

inline int query(int t, int l, int r){
	int ans = -1;
	for(l += 700,r += 700;l < r;l >>= 1, r >>= 1){
		if(l&1){
			ans = max(ans,tree[t][l]);
			l++;
		}
		if(r&1){
			r--;
			ans = max(ans,tree[t][r]);
		}
	}
	return ans;
}
 
 
long long count_rectangles(std::vector<std::vector<int> > a) {
	int rows = a.size();
	int cols = a[0].size();
	long long ans = 0;
	//Segment hori[rows];
	//Segment vert[cols];
 
	set<long long> answers;
	for(int c = 0;c < cols;c++){
		//vert[c].create(rows);
	}
	for(int r = 0;r < rows;r++){
		//hori[r].create(cols);
 
	}
	for(int r = 0;r < rows;r++){
		for(int c = 0;c < cols;c++){
			//hori[r].update(c,a[r][c]);
			//vert[c].update(r,a[r][c]);
			update(r,c,a[r][c]);
			update(rows+c,r,a[r][c]);
		}
	}
	typedef pair<int,int> ii;
	typedef pair<int,ii> iii;
	
	vector<iii> points;
	for(int r = 0;r < rows;r++){
		for(int c = 0;c < cols;c++){
			points.push_back(iii(a[r][c],ii(r,c)));
		}
	}
	
	sort(points.begin(),points.end());
	stack<ii> arr;
	for(int p = 0;p < points.size();p++){
		int rr = points[p].second.first;
		int cc = points[p].second.second;
		//cout << rr << " " << cc << " " << a[rr][cc] << "\n";
		arr.push(ii(rr,cc));
		if(p == points.size()-1 || points[p].first != points[p+1].first){
			while(!arr.empty()){
				int r = arr.top().first;
				int c = arr.top().second;
				arr.pop();
				if(r == 0 || r == rows - 1 || c == 0 || c == cols-1) continue;
				
				//if(hhh[r].query(c) != 0) continue;
				
				int lr = r, hr = r, lc = c, hc = c; //exclusive
				
				while(lr > 0){
					if(a[lr][c] > a[r][c]) break;
					lr--;
				}
				
				while(hr < rows-1){
					if(a[hr][c] > a[r][c]) break;
					hr++;
				}
				
				while(lc > 0){
					if(a[r][lc] > a[r][c]) break;
					lc--;
				}
				
				while(hc < cols-1){
					if(a[r][hc] > a[r][c]) break;
					hc++;
				}
				
				bool can = true;
				for(int sr = lr+1;sr < hr;sr++){
					int value = query(sr,lc+1,hc);
					if(value >= a[sr][lc] || value >= a[sr][hc]){
						can = false;
						break;
					}
				}
				for(int sc = lc+1;sc < hc;sc++){
					int value = query(sc+rows,lr+1,hr);
					if(value >= a[lr][sc] || value >= a[hr][sc]){
						can = false;
						break;
					}
				}
				
				if(can){
					
					long long vvv = lr * 1000000000ll;
					vvv += hr * 1000000ll;
					vvv += lc * 1000ll;
					vvv += hc;
					answers.insert(vvv);
				}
				
				//cout << r << " " << c << " " << lr << " " << hr << " " << lc << " " << hc << "\n";
			}
			
		}
	}
	return answers.size();
}

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:101:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int p = 0;p < points.size();p++){
                ~~^~~~~~~~~~~~~~~
rect.cpp:106:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(p == points.size()-1 || points[p].first != points[p+1].first){
      ~~^~~~~~~~~~~~~~~~~~
rect.cpp:69:12: warning: unused variable 'ans' [-Wunused-variable]
  long long ans = 0;
            ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 4 ms 660 KB Output is correct
11 Correct 3 ms 632 KB Output is correct
12 Correct 3 ms 632 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 3 ms 632 KB Output is correct
20 Correct 3 ms 632 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 4 ms 660 KB Output is correct
11 Correct 3 ms 632 KB Output is correct
12 Correct 3 ms 632 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 14 ms 1656 KB Output is correct
18 Correct 14 ms 1656 KB Output is correct
19 Correct 14 ms 1660 KB Output is correct
20 Correct 6 ms 1400 KB Output is correct
21 Correct 6 ms 1400 KB Output is correct
22 Correct 6 ms 1400 KB Output is correct
23 Correct 6 ms 1404 KB Output is correct
24 Correct 4 ms 1148 KB Output is correct
25 Correct 2 ms 256 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 3 ms 632 KB Output is correct
28 Correct 3 ms 632 KB Output is correct
29 Correct 2 ms 376 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 4 ms 660 KB Output is correct
11 Correct 3 ms 632 KB Output is correct
12 Correct 3 ms 632 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 14 ms 1656 KB Output is correct
18 Correct 14 ms 1656 KB Output is correct
19 Correct 14 ms 1660 KB Output is correct
20 Correct 6 ms 1400 KB Output is correct
21 Correct 6 ms 1400 KB Output is correct
22 Correct 6 ms 1400 KB Output is correct
23 Correct 6 ms 1404 KB Output is correct
24 Correct 4 ms 1148 KB Output is correct
25 Correct 211 ms 5220 KB Output is correct
26 Correct 211 ms 5236 KB Output is correct
27 Correct 209 ms 5356 KB Output is correct
28 Correct 22 ms 3828 KB Output is correct
29 Correct 25 ms 4080 KB Output is correct
30 Correct 25 ms 4080 KB Output is correct
31 Correct 29 ms 4076 KB Output is correct
32 Correct 27 ms 4080 KB Output is correct
33 Correct 2 ms 256 KB Output is correct
34 Correct 2 ms 376 KB Output is correct
35 Correct 3 ms 632 KB Output is correct
36 Correct 3 ms 632 KB Output is correct
37 Correct 2 ms 376 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 4 ms 660 KB Output is correct
11 Correct 3 ms 632 KB Output is correct
12 Correct 3 ms 632 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 14 ms 1656 KB Output is correct
18 Correct 14 ms 1656 KB Output is correct
19 Correct 14 ms 1660 KB Output is correct
20 Correct 6 ms 1400 KB Output is correct
21 Correct 6 ms 1400 KB Output is correct
22 Correct 6 ms 1400 KB Output is correct
23 Correct 6 ms 1404 KB Output is correct
24 Correct 4 ms 1148 KB Output is correct
25 Correct 211 ms 5220 KB Output is correct
26 Correct 211 ms 5236 KB Output is correct
27 Correct 209 ms 5356 KB Output is correct
28 Correct 22 ms 3828 KB Output is correct
29 Correct 25 ms 4080 KB Output is correct
30 Correct 25 ms 4080 KB Output is correct
31 Correct 29 ms 4076 KB Output is correct
32 Correct 27 ms 4080 KB Output is correct
33 Correct 571 ms 18468 KB Output is correct
34 Correct 606 ms 18656 KB Output is correct
35 Correct 598 ms 18532 KB Output is correct
36 Correct 607 ms 18532 KB Output is correct
37 Execution timed out 5077 ms 30420 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 16120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 79 ms 47964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 4 ms 660 KB Output is correct
11 Correct 3 ms 632 KB Output is correct
12 Correct 3 ms 632 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 14 ms 1656 KB Output is correct
18 Correct 14 ms 1656 KB Output is correct
19 Correct 14 ms 1660 KB Output is correct
20 Correct 6 ms 1400 KB Output is correct
21 Correct 6 ms 1400 KB Output is correct
22 Correct 6 ms 1400 KB Output is correct
23 Correct 6 ms 1404 KB Output is correct
24 Correct 4 ms 1148 KB Output is correct
25 Correct 211 ms 5220 KB Output is correct
26 Correct 211 ms 5236 KB Output is correct
27 Correct 209 ms 5356 KB Output is correct
28 Correct 22 ms 3828 KB Output is correct
29 Correct 25 ms 4080 KB Output is correct
30 Correct 25 ms 4080 KB Output is correct
31 Correct 29 ms 4076 KB Output is correct
32 Correct 27 ms 4080 KB Output is correct
33 Correct 571 ms 18468 KB Output is correct
34 Correct 606 ms 18656 KB Output is correct
35 Correct 598 ms 18532 KB Output is correct
36 Correct 607 ms 18532 KB Output is correct
37 Execution timed out 5077 ms 30420 KB Time limit exceeded
38 Halted 0 ms 0 KB -