| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1030972 |
2024-07-22T13:06:32 Z |
Zicrus |
Rectangles (IOI19_rect) |
C++17 |
|
4054 ms |
454664 KB |
#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
typedef long long ll;
ll n, m;
ll pow2N, pow2M;
vector<vector<ll>> segN, segM;
ll segMaxN(ll low, ll high, ll m) {
low += pow2N; high += pow2N;
ll mx = 0;
while (low <= high) {
if (low & 1) mx = max(mx, segN[m][low++]);
if (!(high & 1)) mx = max(mx, segN[m][high--]);
low /= 2; high /= 2;
}
return mx;
}
ll segMaxM(ll low, ll high, ll n) {
low += pow2M; high += pow2M;
ll mx = 0;
while (low <= high) {
if (low & 1) mx = max(mx, segM[n][low++]);
if (!(high & 1)) mx = max(mx, segM[n][high--]);
low /= 2; high /= 2;
}
return mx;
}
ll count_rectangles(vector<vector<int>> a) {
if (a.size() <= 2) return 0;
n = a.size(); m = a[0].size();
pow2N = 1ll << (ll)ceil(log2(n));
pow2M = 1ll << (ll)ceil(log2(m));
vector<int> am = a[1];
segN = vector<vector<ll>>(m, vector<ll>(2*pow2N));
segM = vector<vector<ll>>(n, vector<ll>(2*pow2M));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
segN[j][pow2N+i] = a[i][j];
segM[i][pow2M+j] = a[i][j];
}
}
for (int meta = 0; meta < n; meta++) {
for (int i = pow2M-1; i > 0; i--) {
segM[meta][i] = max(segM[meta][2*i], segM[meta][2*i+1]);
}
}
for (int meta = 0; meta < m; meta++) {
for (int i = pow2N-1; i > 0; i--) {
segN[meta][i] = max(segN[meta][2*i], segN[meta][2*i+1]);
}
}
unordered_set<ll> s;
ll res = 0;
for (int i = 1; i < n-1; i++) {
for (int j = 1; j < m-1; j++) {
ll left = j, right = j, top = i, bottom = i;
ll ref = a[i][j];
while (a[i][left] <= ref && left > 0) left--; left++;
while (a[i][right] <= ref && right < m-1) right++; right--;
while (a[top][j] <= ref && top > 0) top--; top++;
while (a[bottom][j] <= ref && bottom < n-1) bottom++; bottom--;
ll hash = (left << 48) | (right << 32) | (top << 16) | bottom;
if (s.count(hash)) continue;
s.insert(hash);
ll lN = bottom-top+1, lM = right-left+1;
bool poss = 1;
for (int meta = i; meta < i+lN && poss; meta++) {
ll border = min(a[meta][j-1], a[meta][j+lM]);
if (border <= segMaxM(j, j+lM-1, meta)) {
poss = 0;
}
}
for (int meta = j; meta < j+lM && poss; meta++) {
ll border = min(a[i-1][meta], a[i+lN][meta]);
if (border <= segMaxN(i, i+lN-1, meta)) {
poss = 0;
}
}
res += poss;
}
}
return res;
}
Compilation message
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:65:13: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
65 | while (a[i][left] <= ref && left > 0) left--; left++;
| ^~~~~
rect.cpp:65:59: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
65 | while (a[i][left] <= ref && left > 0) left--; left++;
| ^~~~
rect.cpp:66:13: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
66 | while (a[i][right] <= ref && right < m-1) right++; right--;
| ^~~~~
rect.cpp:66:64: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
66 | while (a[i][right] <= ref && right < m-1) right++; right--;
| ^~~~~
rect.cpp:67:13: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
67 | while (a[top][j] <= ref && top > 0) top--; top++;
| ^~~~~
rect.cpp:67:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
67 | while (a[top][j] <= ref && top > 0) top--; top++;
| ^~~
rect.cpp:68:13: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
68 | while (a[bottom][j] <= ref && bottom < n-1) bottom++; bottom--;
| ^~~~~
rect.cpp:68:67: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
68 | while (a[bottom][j] <= ref && bottom < n-1) bottom++; bottom--;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
860 KB |
Output is correct |
| 2 |
Correct |
10 ms |
860 KB |
Output is correct |
| 3 |
Correct |
4 ms |
860 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
600 KB |
Output is correct |
| 2 |
Runtime error |
4054 ms |
454664 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
