| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1047803 |
2024-08-07T16:05:01 Z |
vjudge1 |
Rectangles (IOI19_rect) |
C++17 |
|
123 ms |
98712 KB |
#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define ff first
#define all(x) x.begin(), x.end()
#define ss second
const int N = 2600, K = 20;
int rmqq[N][K];
int rmq[N][N][K], rmq2[N][N][K];
int get(int l, int r){
int k = int(log2(r-l+1));
return max(rmqq[l][k], rmqq[r-(1<<k)+1][k]);
}
int gett(int l, int r, int sat){
int k = int(log2(r-l+1));
return max(rmq2[sat][l][k], rmq2[sat][r-(1<<k)+1][k]);
}
int gett2(int l, int r, int sat){
int k = int(log2(r-l+1));
return max(rmq[sat][l][k], rmq[sat][r-(1<<k)+1][k]);
}
long long count_rectangles(std::vector<std::vector<int> > a) {
int n = a.size();
int m = a[0].size();
if(n < 3 || m < 3){
return 0;
}
if(n == 3){
vector<bool> good(m);
for(int i = 1; i + 1 < m; ++i){
if(a[1][i] < a[0][i] && a[1][i] < a[2][i]){
good[i] = 1;
}else good[i] = 0;
}
for(int i = 1; i < m; ++i) rmqq[i][0] = (good[i] ? a[1][i] : INT_MAX);
for(int j = 1; j < K; ++j){
for(int i = 1; i + (1<<j) <= m; ++i){
rmqq[i][j] = max(rmqq[i][j - 1], rmqq[i+(1<<(j-1))][j-1]);
}
}
int ans = 0;
for(int i = 1; i + 1 < m; ++i){
for(int j = i; j + 1 < m; ++j){
if(get(i, j) < min(a[1][i - 1], a[1][j + 1]) && good[i]){
++ans;
}
}
}
return ans;
}
int mx = 0;
for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) mx = max(mx, a[i][j]);
if(mx <= 1){
vector<vector<int>> dp(n, vector<int>(m));
vector<vector<int>> dp2(n, vector<int>(m));
ll ans = 0;
for(int j = 1; j + 1 < m; ++j) dp[0][j] = (a[0][j] == 0 ? -n*m*5 : 0);
for(int i = 1; i + 1 < n; ++i){
for(int j = 0; j < m; ++j){
if(a[i][j] == 1){
dp[i][j] = 0;
dp2[i][j] = dp2[i - 1][j] + 1;
}else{
dp[i][j] = dp[i - 1][j] + 1;
dp2[i][j] = 0;
}
}
}
// for(int i = 0; i < n; ++i){
// for(int j = 0; j < m; ++j) cout << a[i][j];
// cout << '\n';
// }
for(int i = 1; i + 1 < n; ++i){
int r = 1;
for(int j = 1; j + 1 < m; ++j){
// cout << i << ' ' << j << '\n';
if(a[i][j] == 1) continue;
// cout << i << ' ' << j << '\n';
if(a[i][j - 1] != 1) continue;
if(a[i + 1][j] != 1) continue;
r = j;
while(r + 1 < m && a[i][r] == 0 && a[i + 1][r] == 1) ++r;
--r;
if(a[i][r + 1] != 1){
j = r;
continue;
}
ll sum = 0;
int mx = dp[i][j];
if(mx < 0){
j = r;
continue;
}
int ok = 1;
vector<pair<int, ll>> v;
for(int l = j; l <= r; ++l){
// int co = 1;
// while(!v.empty() && v.back().first > dp[i][l]){
// co += v.back().second;
// sum -= v.back().first * v.back().second;
// v.pop_back();
// }
// sum += dp[i][l] * co;
// v.pb({dp[i][l], co});
if(dp[i][l] != mx) ok = 0;
}
// cout << ok;
// cout << i << ' ' << j-1 << ' ';
// cout <<dp2[i][j-1] << ' ';
ans += ok && dp2[i][j - 1] >= dp[i][j] && dp2[i][r + 1] >= dp[i][j];
// cout << i << ' ' << j << ' ' << r << ' ' << ans << '\n';
j = r;
}
}
return ans;
}
for(int l = 0; l < n; ++l){
for(int i = 0; i < m; ++i) rmq[l][i + 1][0] = a[l][i];
for(int j = 1; j < K; ++j){
for(int i = 1; i + (1<<j) <= m + 1; ++i){
rmq[l][i][j] = max(rmq[l][i][j - 1], rmq[l][i+(1<<(j-1))][j-1]);
}
}
}
for(int l = 0; l < m; ++l){
for(int i = 0; i < m; ++i) rmq2[l][i + 1][0] = a[i][l];
for(int j = 1; j < K; ++j){
for(int i = 1; i + (1<<j) <= n + 1; ++i){
rmq2[l][i][j] = max(rmq2[l][i][j - 1], rmq2[l][i+(1<<(j-1))][j-1]);
}
}
}
int ans = 0;
for(int i =1; i + 1< n; ++i){
for(int i1 = i; i1 + 1 < n; ++i1){
for(int j = 1; j + 1 < m; ++j){
for(int j1 = j; j1 + 1 < m; ++j1){
bool ok = 1;
for(int l = j; l <= j1; ++l){
if(gett(i, i1, l) >= min(a[i1 + 1][l], a[i - 1][l])){
ok = 0;
}
}
for(int l = i; l <= i1; ++l){
if(gett2(j, j1, l) >= min(a[l][j1 + 1], a[l][j - 1])){
ok = 0;
}
}
ans += ok;
}
}
}
}
return ans;
}
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:96:8: warning: unused variable 'sum' [-Wunused-variable]
96 | ll sum = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
604 KB |
Output is correct |
| 2 |
Correct |
23 ms |
604 KB |
Output is correct |
| 3 |
Correct |
30 ms |
604 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
30 ms |
604 KB |
Output is correct |
| 6 |
Correct |
31 ms |
604 KB |
Output is correct |
| 7 |
Correct |
31 ms |
604 KB |
Output is correct |
| 8 |
Correct |
38 ms |
680 KB |
Output is correct |
| 9 |
Correct |
31 ms |
600 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
57 ms |
45444 KB |
Output is correct |
| 3 |
Correct |
119 ms |
98092 KB |
Output is correct |
| 4 |
Correct |
119 ms |
98644 KB |
Output is correct |
| 5 |
Correct |
123 ms |
98712 KB |
Output is correct |
| 6 |
Correct |
37 ms |
48720 KB |
Output is correct |
| 7 |
Correct |
107 ms |
92496 KB |
Output is correct |
| 8 |
Correct |
75 ms |
98452 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
