# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
152079 |
2019-09-06T10:20:46 Z |
oolimry |
Rectangles (IOI19_rect) |
C++14 |
|
1465 ms |
230700 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 hh[201][201][201];
static int vv[201][201][201];
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 i = 0;i < cols;i++){
for(int j = i;j < cols;j++){
if(i == j) hh[r][i][j] = a[r][i];
else hh[r][i][j] = max(hh[r][i][j-1],a[r][j]);
}
}
}
for(int c = 0;c < cols;c++){
for(int i = 0;i < rows;i++){
for(int j = i;j < rows;j++){
if(i == j) vv[c][i][j] = a[i][c];
else vv[c][i][j] = max(vv[c][i][j-1],a[j][c]);
}
}
}
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]);
}
}
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 = hori[sr].query(lc+1,hc);
int value = hh[sr][lc+1][hc-1];
if(value >= a[sr][lc] || value >= a[sr][hc]){
can = false;
break;
}
}
for(int sc = lc+1;sc < hc;sc++){
//int value = vert[sc].query(lr+1,hr);
int value = vv[sc][lr+1][hr-1];
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:92:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int p = 0;p < points.size();p++){
~~^~~~~~~~~~~~~~~
rect.cpp:97: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:46:12: warning: unused variable 'ans' [-Wunused-variable]
long long ans = 0;
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
4 ms |
2040 KB |
Output is correct |
3 |
Correct |
4 ms |
2040 KB |
Output is correct |
4 |
Correct |
4 ms |
2040 KB |
Output is correct |
5 |
Correct |
4 ms |
2040 KB |
Output is correct |
6 |
Correct |
4 ms |
2044 KB |
Output is correct |
7 |
Correct |
3 ms |
1144 KB |
Output is correct |
8 |
Correct |
3 ms |
1016 KB |
Output is correct |
9 |
Correct |
4 ms |
2040 KB |
Output is correct |
10 |
Correct |
4 ms |
2040 KB |
Output is correct |
11 |
Correct |
4 ms |
2040 KB |
Output is correct |
12 |
Correct |
4 ms |
2040 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
348 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 |
2040 KB |
Output is correct |
20 |
Correct |
3 ms |
1144 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
4 ms |
2040 KB |
Output is correct |
3 |
Correct |
4 ms |
2040 KB |
Output is correct |
4 |
Correct |
4 ms |
2040 KB |
Output is correct |
5 |
Correct |
4 ms |
2040 KB |
Output is correct |
6 |
Correct |
4 ms |
2044 KB |
Output is correct |
7 |
Correct |
3 ms |
1144 KB |
Output is correct |
8 |
Correct |
3 ms |
1016 KB |
Output is correct |
9 |
Correct |
4 ms |
2040 KB |
Output is correct |
10 |
Correct |
4 ms |
2040 KB |
Output is correct |
11 |
Correct |
4 ms |
2040 KB |
Output is correct |
12 |
Correct |
4 ms |
2040 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
504 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
18 ms |
11612 KB |
Output is correct |
18 |
Correct |
18 ms |
11512 KB |
Output is correct |
19 |
Correct |
19 ms |
11640 KB |
Output is correct |
20 |
Correct |
14 ms |
11384 KB |
Output is correct |
21 |
Correct |
15 ms |
11256 KB |
Output is correct |
22 |
Correct |
14 ms |
11256 KB |
Output is correct |
23 |
Correct |
15 ms |
11384 KB |
Output is correct |
24 |
Correct |
8 ms |
6008 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 |
2040 KB |
Output is correct |
28 |
Correct |
3 ms |
1144 KB |
Output is correct |
29 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
4 ms |
2040 KB |
Output is correct |
3 |
Correct |
4 ms |
2040 KB |
Output is correct |
4 |
Correct |
4 ms |
2040 KB |
Output is correct |
5 |
Correct |
4 ms |
2040 KB |
Output is correct |
6 |
Correct |
4 ms |
2044 KB |
Output is correct |
7 |
Correct |
3 ms |
1144 KB |
Output is correct |
8 |
Correct |
3 ms |
1016 KB |
Output is correct |
9 |
Correct |
4 ms |
2040 KB |
Output is correct |
10 |
Correct |
4 ms |
2040 KB |
Output is correct |
11 |
Correct |
4 ms |
2040 KB |
Output is correct |
12 |
Correct |
4 ms |
2040 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
504 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
18 ms |
11612 KB |
Output is correct |
18 |
Correct |
18 ms |
11512 KB |
Output is correct |
19 |
Correct |
19 ms |
11640 KB |
Output is correct |
20 |
Correct |
14 ms |
11384 KB |
Output is correct |
21 |
Correct |
15 ms |
11256 KB |
Output is correct |
22 |
Correct |
14 ms |
11256 KB |
Output is correct |
23 |
Correct |
15 ms |
11384 KB |
Output is correct |
24 |
Correct |
8 ms |
6008 KB |
Output is correct |
25 |
Correct |
202 ms |
67000 KB |
Output is correct |
26 |
Correct |
204 ms |
66996 KB |
Output is correct |
27 |
Correct |
203 ms |
67052 KB |
Output is correct |
28 |
Correct |
88 ms |
65652 KB |
Output is correct |
29 |
Correct |
102 ms |
65780 KB |
Output is correct |
30 |
Correct |
95 ms |
65776 KB |
Output is correct |
31 |
Correct |
94 ms |
65776 KB |
Output is correct |
32 |
Correct |
95 ms |
65396 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 |
2040 KB |
Output is correct |
36 |
Correct |
3 ms |
1144 KB |
Output is correct |
37 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
4 ms |
2040 KB |
Output is correct |
3 |
Correct |
4 ms |
2040 KB |
Output is correct |
4 |
Correct |
4 ms |
2040 KB |
Output is correct |
5 |
Correct |
4 ms |
2040 KB |
Output is correct |
6 |
Correct |
4 ms |
2044 KB |
Output is correct |
7 |
Correct |
3 ms |
1144 KB |
Output is correct |
8 |
Correct |
3 ms |
1016 KB |
Output is correct |
9 |
Correct |
4 ms |
2040 KB |
Output is correct |
10 |
Correct |
4 ms |
2040 KB |
Output is correct |
11 |
Correct |
4 ms |
2040 KB |
Output is correct |
12 |
Correct |
4 ms |
2040 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
504 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
18 ms |
11612 KB |
Output is correct |
18 |
Correct |
18 ms |
11512 KB |
Output is correct |
19 |
Correct |
19 ms |
11640 KB |
Output is correct |
20 |
Correct |
14 ms |
11384 KB |
Output is correct |
21 |
Correct |
15 ms |
11256 KB |
Output is correct |
22 |
Correct |
14 ms |
11256 KB |
Output is correct |
23 |
Correct |
15 ms |
11384 KB |
Output is correct |
24 |
Correct |
8 ms |
6008 KB |
Output is correct |
25 |
Correct |
202 ms |
67000 KB |
Output is correct |
26 |
Correct |
204 ms |
66996 KB |
Output is correct |
27 |
Correct |
203 ms |
67052 KB |
Output is correct |
28 |
Correct |
88 ms |
65652 KB |
Output is correct |
29 |
Correct |
102 ms |
65780 KB |
Output is correct |
30 |
Correct |
95 ms |
65776 KB |
Output is correct |
31 |
Correct |
94 ms |
65776 KB |
Output is correct |
32 |
Correct |
95 ms |
65396 KB |
Output is correct |
33 |
Runtime error |
188 ms |
95480 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
34 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
42 ms |
10460 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Runtime error |
1465 ms |
230700 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
4 ms |
2040 KB |
Output is correct |
3 |
Correct |
4 ms |
2040 KB |
Output is correct |
4 |
Correct |
4 ms |
2040 KB |
Output is correct |
5 |
Correct |
4 ms |
2040 KB |
Output is correct |
6 |
Correct |
4 ms |
2044 KB |
Output is correct |
7 |
Correct |
3 ms |
1144 KB |
Output is correct |
8 |
Correct |
3 ms |
1016 KB |
Output is correct |
9 |
Correct |
4 ms |
2040 KB |
Output is correct |
10 |
Correct |
4 ms |
2040 KB |
Output is correct |
11 |
Correct |
4 ms |
2040 KB |
Output is correct |
12 |
Correct |
4 ms |
2040 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
348 KB |
Output is correct |
15 |
Correct |
2 ms |
504 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
18 ms |
11612 KB |
Output is correct |
18 |
Correct |
18 ms |
11512 KB |
Output is correct |
19 |
Correct |
19 ms |
11640 KB |
Output is correct |
20 |
Correct |
14 ms |
11384 KB |
Output is correct |
21 |
Correct |
15 ms |
11256 KB |
Output is correct |
22 |
Correct |
14 ms |
11256 KB |
Output is correct |
23 |
Correct |
15 ms |
11384 KB |
Output is correct |
24 |
Correct |
8 ms |
6008 KB |
Output is correct |
25 |
Correct |
202 ms |
67000 KB |
Output is correct |
26 |
Correct |
204 ms |
66996 KB |
Output is correct |
27 |
Correct |
203 ms |
67052 KB |
Output is correct |
28 |
Correct |
88 ms |
65652 KB |
Output is correct |
29 |
Correct |
102 ms |
65780 KB |
Output is correct |
30 |
Correct |
95 ms |
65776 KB |
Output is correct |
31 |
Correct |
94 ms |
65776 KB |
Output is correct |
32 |
Correct |
95 ms |
65396 KB |
Output is correct |
33 |
Runtime error |
188 ms |
95480 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
34 |
Halted |
0 ms |
0 KB |
- |