# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
200944 |
2020-02-08T18:26:05 Z |
Lawliet |
Rectangles (IOI19_rect) |
C++17 |
|
5000 ms |
56952 KB |
#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
typedef long long int lli;
typedef pair<int,int> pii;
const int MAXN = 210;
const int INF = 1000000010;
int n, m;
int v[MAXN][MAXN];
int L[MAXN][MAXN];
int R[MAXN][MAXN];
int up[MAXN][MAXN];
int down[MAXN][MAXN];
vector< bool > isPossibleLine[MAXN][MAXN];
vector< bool > isPossibleColumn[MAXN][MAXN];
void makeHistogram()
{
for(int i = 1 ; i <= n ; i++)
{
L[i][1] = 0;
R[i][m] = m + 1;
v[i][0] = v[i][m + 1] = INF;
for(int j = 2 ; j <= m ; j++)
{
int cur = j - 1;
while( v[i][cur] < v[i][j] ) cur = L[i][cur];
L[i][j] = cur;
}
for(int j = m - 1 ; j > 0 ; j--)
{
int cur = j + 1;
while( v[i][cur] <= v[i][j] ) cur = R[i][cur];
R[i][j] = cur;
}
}
for(int j = 1 ; j <= m ; j++)
{
up[1][j] = 0;
down[n][j] = n + 1;
v[0][j] = v[n + 1][j] = INF;
for(int i = 2 ; i <= n ; i++)
{
int cur = i - 1;
while( v[cur][j] < v[i][j] ) cur = up[cur][j];
up[i][j] = cur;
}
for(int i = n - 1 ; i > 0 ; i--)
{
int cur = i + 1;
while( v[cur][j] <= v[i][j] ) cur = down[cur][j];
down[i][j] = cur;
}
}
}
void preProcess()
{
for(int i = 1 ; i <= m ; i++)
for(int j = 1 ; j <= m ; j++)
isPossibleLine[i][j].push_back( false ), isPossibleLine[i][j].push_back( false );//Nesse intervalo de colunas, consigo essa linha?
for(int i = 2 ; i < n ; i++)
{
for(int y1 = 2 ; y1 < m ; y1++)//Ver m == 2 ou m == 3
{
int mx = v[i][y1];
for(int y2 = y1 ; y2 < m ; y2++)
{
if( mx < v[i][y1 - 1] && mx < v[i][y2 + 1] ) isPossibleLine[y1][y2].push_back( true );
else isPossibleLine[y1][y2].push_back( false );
if( y2 >= m - 1 ) break;
mx = max( mx , v[i][y2 + 1] );
}
}
}
for(int i = 1 ; i <= m ; i++)
for(int j = 1 ; j <= m ; j++)
isPossibleLine[i][j].push_back( false );
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= n ; j++)
isPossibleColumn[i][j].push_back( false ), isPossibleColumn[i][j].push_back( false );
for(int i = 2 ; i < m ; i++)
{
for(int x1 = 2 ; x1 < n ; x1++)//Ver n == 2 ou n == 3
{
int mx = v[x1][i];
for(int x2 = x1 ; x2 < n ; x2++)
{
if( mx < v[x1 - 1][i] && mx < v[x2 + 1][i] ) isPossibleColumn[x1][x2].push_back( true );
else isPossibleColumn[x1][x2].push_back( false );
if( x2 >= n - 1 ) break;
mx = max( mx , v[x2 + 1][i] );
}
}
}
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= n ; j++)
isPossibleColumn[i][j].push_back( false );
}
bool isAnswer(int x1, int y1, int x2, int y2)
{
for(int i = x1 ; i <= x2 ; i++)
if( !isPossibleLine[y1][y2][i] ) return false;
for(int i = y1 ; i <= y2 ; i++)
if( !isPossibleColumn[x1][x2][i] ) return false;
return true;
}
long long count_rectangles(vector< vector<int> > a) //Grids pequenos
{
n = a.size();
m = a[0].size();
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < m ; j++)
v[i + 1][j + 1] = a[i][j];
makeHistogram();
vector< pair<pii,pii> > aux;
vector< pair<pii,pii> > rect;
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= m ; j++)
{
if( L[i][j] == 0 ) continue;
if( R[i][j] == m + 1 ) continue;
if( up[i][j] == 0 ) continue;
if( down[i][j] == n + 1 ) continue;
pii dY = { L[i][j] + 1 , R[i][j] - 1 };
pii dX = { up[i][j] + 1 , down[i][j] - 1 };
aux.push_back( { dX , dY } );
}
}
preProcess();
sort( aux.begin() , aux.end() );
for(int i = 0 ; i < aux.size() ; i++)
if( i == 0 || aux[i] != aux[i - 1] ) rect.push_back( { aux[i] } );
lli ans = 0;
for(int i = 0 ; i < rect.size() ; i++)
{
int x1 = rect[i].first.first;
int x2 = rect[i].first.second;
int y1 = rect[i].second.first;
int y2 = rect[i].second.second;
if( isAnswer( x1 , y1 , x2 , y2 ) ) ans++;
}
return ans;
}
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:178:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < aux.size() ; i++)
~~^~~~~~~~~~~~
rect.cpp:183:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < rect.size() ; i++)
~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
3832 KB |
Output is correct |
2 |
Correct |
7 ms |
3960 KB |
Output is correct |
3 |
Correct |
7 ms |
3960 KB |
Output is correct |
4 |
Correct |
7 ms |
3960 KB |
Output is correct |
5 |
Correct |
7 ms |
3960 KB |
Output is correct |
6 |
Correct |
7 ms |
4088 KB |
Output is correct |
7 |
Correct |
8 ms |
3960 KB |
Output is correct |
8 |
Correct |
7 ms |
3832 KB |
Output is correct |
9 |
Correct |
7 ms |
3960 KB |
Output is correct |
10 |
Correct |
7 ms |
3960 KB |
Output is correct |
11 |
Correct |
7 ms |
3960 KB |
Output is correct |
12 |
Correct |
7 ms |
3960 KB |
Output is correct |
13 |
Correct |
7 ms |
3832 KB |
Output is correct |
14 |
Correct |
7 ms |
3832 KB |
Output is correct |
15 |
Correct |
7 ms |
3832 KB |
Output is correct |
16 |
Correct |
7 ms |
3836 KB |
Output is correct |
17 |
Correct |
7 ms |
3832 KB |
Output is correct |
18 |
Correct |
7 ms |
3832 KB |
Output is correct |
19 |
Correct |
7 ms |
3960 KB |
Output is correct |
20 |
Correct |
7 ms |
3960 KB |
Output is correct |
21 |
Correct |
8 ms |
3832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
3832 KB |
Output is correct |
2 |
Correct |
7 ms |
3960 KB |
Output is correct |
3 |
Correct |
7 ms |
3960 KB |
Output is correct |
4 |
Correct |
7 ms |
3960 KB |
Output is correct |
5 |
Correct |
7 ms |
3960 KB |
Output is correct |
6 |
Correct |
7 ms |
4088 KB |
Output is correct |
7 |
Correct |
8 ms |
3960 KB |
Output is correct |
8 |
Correct |
7 ms |
3832 KB |
Output is correct |
9 |
Correct |
7 ms |
3960 KB |
Output is correct |
10 |
Correct |
7 ms |
3960 KB |
Output is correct |
11 |
Correct |
7 ms |
3960 KB |
Output is correct |
12 |
Correct |
7 ms |
3960 KB |
Output is correct |
13 |
Correct |
7 ms |
3832 KB |
Output is correct |
14 |
Correct |
7 ms |
3832 KB |
Output is correct |
15 |
Correct |
7 ms |
3832 KB |
Output is correct |
16 |
Correct |
7 ms |
3836 KB |
Output is correct |
17 |
Correct |
12 ms |
4856 KB |
Output is correct |
18 |
Correct |
11 ms |
4856 KB |
Output is correct |
19 |
Correct |
11 ms |
4856 KB |
Output is correct |
20 |
Correct |
13 ms |
4776 KB |
Output is correct |
21 |
Correct |
12 ms |
4856 KB |
Output is correct |
22 |
Correct |
11 ms |
4856 KB |
Output is correct |
23 |
Correct |
11 ms |
4856 KB |
Output is correct |
24 |
Correct |
9 ms |
4472 KB |
Output is correct |
25 |
Correct |
7 ms |
3832 KB |
Output is correct |
26 |
Correct |
7 ms |
3832 KB |
Output is correct |
27 |
Correct |
7 ms |
3960 KB |
Output is correct |
28 |
Correct |
7 ms |
3960 KB |
Output is correct |
29 |
Correct |
8 ms |
3832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
3832 KB |
Output is correct |
2 |
Correct |
7 ms |
3960 KB |
Output is correct |
3 |
Correct |
7 ms |
3960 KB |
Output is correct |
4 |
Correct |
7 ms |
3960 KB |
Output is correct |
5 |
Correct |
7 ms |
3960 KB |
Output is correct |
6 |
Correct |
7 ms |
4088 KB |
Output is correct |
7 |
Correct |
8 ms |
3960 KB |
Output is correct |
8 |
Correct |
7 ms |
3832 KB |
Output is correct |
9 |
Correct |
7 ms |
3960 KB |
Output is correct |
10 |
Correct |
7 ms |
3960 KB |
Output is correct |
11 |
Correct |
7 ms |
3960 KB |
Output is correct |
12 |
Correct |
7 ms |
3960 KB |
Output is correct |
13 |
Correct |
7 ms |
3832 KB |
Output is correct |
14 |
Correct |
7 ms |
3832 KB |
Output is correct |
15 |
Correct |
7 ms |
3832 KB |
Output is correct |
16 |
Correct |
7 ms |
3836 KB |
Output is correct |
17 |
Correct |
12 ms |
4856 KB |
Output is correct |
18 |
Correct |
11 ms |
4856 KB |
Output is correct |
19 |
Correct |
11 ms |
4856 KB |
Output is correct |
20 |
Correct |
13 ms |
4776 KB |
Output is correct |
21 |
Correct |
12 ms |
4856 KB |
Output is correct |
22 |
Correct |
11 ms |
4856 KB |
Output is correct |
23 |
Correct |
11 ms |
4856 KB |
Output is correct |
24 |
Correct |
9 ms |
4472 KB |
Output is correct |
25 |
Correct |
68 ms |
10220 KB |
Output is correct |
26 |
Correct |
61 ms |
10316 KB |
Output is correct |
27 |
Correct |
65 ms |
10348 KB |
Output is correct |
28 |
Correct |
52 ms |
9332 KB |
Output is correct |
29 |
Correct |
55 ms |
10220 KB |
Output is correct |
30 |
Correct |
59 ms |
10224 KB |
Output is correct |
31 |
Correct |
61 ms |
10224 KB |
Output is correct |
32 |
Correct |
61 ms |
10340 KB |
Output is correct |
33 |
Correct |
7 ms |
3832 KB |
Output is correct |
34 |
Correct |
7 ms |
3832 KB |
Output is correct |
35 |
Correct |
7 ms |
3960 KB |
Output is correct |
36 |
Correct |
7 ms |
3960 KB |
Output is correct |
37 |
Correct |
8 ms |
3832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
3832 KB |
Output is correct |
2 |
Correct |
7 ms |
3960 KB |
Output is correct |
3 |
Correct |
7 ms |
3960 KB |
Output is correct |
4 |
Correct |
7 ms |
3960 KB |
Output is correct |
5 |
Correct |
7 ms |
3960 KB |
Output is correct |
6 |
Correct |
7 ms |
4088 KB |
Output is correct |
7 |
Correct |
8 ms |
3960 KB |
Output is correct |
8 |
Correct |
7 ms |
3832 KB |
Output is correct |
9 |
Correct |
7 ms |
3960 KB |
Output is correct |
10 |
Correct |
7 ms |
3960 KB |
Output is correct |
11 |
Correct |
7 ms |
3960 KB |
Output is correct |
12 |
Correct |
7 ms |
3960 KB |
Output is correct |
13 |
Correct |
7 ms |
3832 KB |
Output is correct |
14 |
Correct |
7 ms |
3832 KB |
Output is correct |
15 |
Correct |
7 ms |
3832 KB |
Output is correct |
16 |
Correct |
7 ms |
3836 KB |
Output is correct |
17 |
Correct |
12 ms |
4856 KB |
Output is correct |
18 |
Correct |
11 ms |
4856 KB |
Output is correct |
19 |
Correct |
11 ms |
4856 KB |
Output is correct |
20 |
Correct |
13 ms |
4776 KB |
Output is correct |
21 |
Correct |
12 ms |
4856 KB |
Output is correct |
22 |
Correct |
11 ms |
4856 KB |
Output is correct |
23 |
Correct |
11 ms |
4856 KB |
Output is correct |
24 |
Correct |
9 ms |
4472 KB |
Output is correct |
25 |
Correct |
68 ms |
10220 KB |
Output is correct |
26 |
Correct |
61 ms |
10316 KB |
Output is correct |
27 |
Correct |
65 ms |
10348 KB |
Output is correct |
28 |
Correct |
52 ms |
9332 KB |
Output is correct |
29 |
Correct |
55 ms |
10220 KB |
Output is correct |
30 |
Correct |
59 ms |
10224 KB |
Output is correct |
31 |
Correct |
61 ms |
10224 KB |
Output is correct |
32 |
Correct |
61 ms |
10340 KB |
Output is correct |
33 |
Runtime error |
33 ms |
15608 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 |
Execution timed out |
5050 ms |
3832 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
3832 KB |
Output is correct |
2 |
Runtime error |
78 ms |
56952 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 |
7 ms |
3832 KB |
Output is correct |
2 |
Correct |
7 ms |
3960 KB |
Output is correct |
3 |
Correct |
7 ms |
3960 KB |
Output is correct |
4 |
Correct |
7 ms |
3960 KB |
Output is correct |
5 |
Correct |
7 ms |
3960 KB |
Output is correct |
6 |
Correct |
7 ms |
4088 KB |
Output is correct |
7 |
Correct |
8 ms |
3960 KB |
Output is correct |
8 |
Correct |
7 ms |
3832 KB |
Output is correct |
9 |
Correct |
7 ms |
3960 KB |
Output is correct |
10 |
Correct |
7 ms |
3960 KB |
Output is correct |
11 |
Correct |
7 ms |
3960 KB |
Output is correct |
12 |
Correct |
7 ms |
3960 KB |
Output is correct |
13 |
Correct |
7 ms |
3832 KB |
Output is correct |
14 |
Correct |
7 ms |
3832 KB |
Output is correct |
15 |
Correct |
7 ms |
3832 KB |
Output is correct |
16 |
Correct |
7 ms |
3836 KB |
Output is correct |
17 |
Correct |
12 ms |
4856 KB |
Output is correct |
18 |
Correct |
11 ms |
4856 KB |
Output is correct |
19 |
Correct |
11 ms |
4856 KB |
Output is correct |
20 |
Correct |
13 ms |
4776 KB |
Output is correct |
21 |
Correct |
12 ms |
4856 KB |
Output is correct |
22 |
Correct |
11 ms |
4856 KB |
Output is correct |
23 |
Correct |
11 ms |
4856 KB |
Output is correct |
24 |
Correct |
9 ms |
4472 KB |
Output is correct |
25 |
Correct |
68 ms |
10220 KB |
Output is correct |
26 |
Correct |
61 ms |
10316 KB |
Output is correct |
27 |
Correct |
65 ms |
10348 KB |
Output is correct |
28 |
Correct |
52 ms |
9332 KB |
Output is correct |
29 |
Correct |
55 ms |
10220 KB |
Output is correct |
30 |
Correct |
59 ms |
10224 KB |
Output is correct |
31 |
Correct |
61 ms |
10224 KB |
Output is correct |
32 |
Correct |
61 ms |
10340 KB |
Output is correct |
33 |
Runtime error |
33 ms |
15608 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
34 |
Halted |
0 ms |
0 KB |
- |