| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1073334 |
2024-08-24T12:39:39 Z |
n1k |
Rectangles (IOI19_rect) |
C++17 |
|
1643 ms |
378588 KB |
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<array<int, 3>>> h;
vector<vector<array<int, 2>>> get(){
vector<vector<array<int, 2>>> l(n, vector<array<int, 2>>(m));
for(int r=1; r+1<h.size(); r++){
vector<array<int, 3>> st = {{h[r][0]}};
for(int c=1; c+1<h[0].size(); c++){
while(st.size() and st.back()[0]<=h[r][c][0]){
st.pop_back();
}
l[h[r][c][1]][h[r][c][2]] = (st.size()?array<int, 2>{st.back()[1], st.back()[2]}:array<int, 2>{-1, -1});
st.push_back(h[r][c]);
}
}
return l;
}
void rot(){
vector<vector<array<int, 3>>> hh(h[0].size(), vector<array<int, 3>>(h.size()));
for(int r=0; r<h.size(); r++){
for(int c=0; c<h[0].size(); c++){
hh[c][h.size() - r - 1] = h[r][c];
}
}
h = hh;
}
long long count_rectangles(vector<vector<int>> a) {
n = a.size(), m = a[0].size();
h.assign(a.size(), vector<array<int, 3>>(a[0].size()));
vector<array<int, 3>> order;
for(int r=0; r<a.size(); r++){
for(int c=0; c<a[0].size(); c++){
h[r][c] = {a[r][c], r, c};
}
}
for(int r=1; r+1<a.size(); r++){
for(int c=1; c+1<a[0].size(); c++){
order.push_back({h[r][c][0], r, c});
}
}
sort(order.begin(), order.end());
auto l=get();
rot();
auto d = get();
rot();
auto ri = get();
rot();
auto u = get();
rot();
auto find = [&](int r1, int r2, int c1, int c2){
array<int, 3> ll={int(1e9)}, dd={int(-1e9)}, riri={int(-1e9)}, uu={int(1e9)};
for(int r=r1+1; r<r2; r++){
for(int c=c1+1; c<c2; c++){
ll = min(ll, {l[r][c][1], r, c});
dd = max(dd, {d[r][c][0], r, c});
riri = max(riri, {ri[r][c][1], r, c});
uu = min(uu, {u[r][c][0], r, c});
}
}
set<array<int, 2>> s;
s.insert({ll[1], ll[2]});
s.insert({dd[1], dd[2]});
s.insert({riri[1], riri[2]});
s.insert({uu[1], uu[2]});
return s;
};
vector g(n, vector<vector<array<int, 2>>>(m));
for(int r=1; r+1<n; r++){
for(int c=1; c+1<m; c++){
// find()
int r1 = u[r][c][0], r2 = d[r][c][0];
int c1 = l[r][c][1], c2 = ri[r][c][1];
if(min({r1, r2, c1, c2})==-1){
g[r][c].push_back({-1, -1});
}else{
for(auto p:find(r1, r2, c1, c2)){
g[r][c].push_back(p);
}
}
}
}
vector mem(n, vector<int>(m, -1));
vector vis(n, vector<int>(m));
function<void(int, int)> dfs = [&](int r, int c){
if(vis[r][c]) return;
vis[r][c]=1;
if(mem[r][c]!=-1) mem[r][c];
bool ok = 1;
for(auto [rr, cc]:g[r][c]){
if(rr==r and cc==c){
continue;
}
if(rr==-1 and cc==-1){
ok = 0;
break;
}
dfs(rr, cc);
ok &= mem[rr][cc];
l[r][c][1] = min(l[r][c][1], l[rr][cc][1]);
d[r][c][0] = max(d[r][c][0], d[rr][cc][0]);
ri[r][c][1] = max(ri[r][c][1], ri[rr][cc][1]);
u[r][c][0] = min(u[r][c][0], u[rr][cc][0]);
}
mem[r][c] = ok;
};
long long ans = 0;
for(auto [_, r, c]:order){
if(vis[r][c]) continue;
dfs(r, c);
assert(mem[r][c]!=-1);
ans += mem[r][c];
if(mem[r][c]){
for(int rr=u[r][c][0]+1; rr<d[r][c][0]; rr++){
for(int cc=l[r][c][1]+1; cc<ri[r][c][1]; cc++){
mem[rr][cc] = mem[r][c];
vis[rr][cc] = 1;
}
}
}
if(mem[r][c]==1){
//cerr<<r<<" "<<c<<" "<<mem[r][c]<<endl;
}
}
// build graph
/*
for(int r=0; r<u.size();r++){
for(int c=0; c<u[0].size(); c++){
cerr<<u[r][c][0]<<" "<<u[r][c][1]<<" | ";
}
cerr<<endl;
}
for(int r=0; r<h.size(); r++){
for(int c=0; c<h[0].size(); c++){
cerr<<h[r][c][0]<<" ";
}
cerr<<endl;
}
*/
return ans;
}
Compilation message
rect.cpp: In function 'std::vector<std::vector<std::array<int, 2> > > get()':
rect.cpp:12:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::array<int, 3> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | for(int r=1; r+1<h.size(); r++){
| ~~~^~~~~~~~~
rect.cpp:14:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for(int c=1; c+1<h[0].size(); c++){
| ~~~^~~~~~~~~~~~
rect.cpp: In function 'void rot()':
rect.cpp:27:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::array<int, 3> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(int r=0; r<h.size(); r++){
| ~^~~~~~~~~
rect.cpp:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int c=0; c<h[0].size(); c++){
| ~^~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int r=0; r<a.size(); r++){
| ~^~~~~~~~~
rect.cpp:40:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int c=0; c<a[0].size(); c++){
| ~^~~~~~~~~~~~
rect.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int r=1; r+1<a.size(); r++){
| ~~~^~~~~~~~~
rect.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int c=1; c+1<a[0].size(); c++){
| ~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
4 ms |
348 KB |
Output is correct |
| 3 |
Correct |
4 ms |
348 KB |
Output is correct |
| 4 |
Correct |
4 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
4 ms |
348 KB |
Output is correct |
| 3 |
Correct |
4 ms |
348 KB |
Output is correct |
| 4 |
Correct |
4 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
4 ms |
348 KB |
Output is correct |
| 3 |
Correct |
4 ms |
348 KB |
Output is correct |
| 4 |
Correct |
4 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
4 ms |
348 KB |
Output is correct |
| 3 |
Correct |
4 ms |
348 KB |
Output is correct |
| 4 |
Correct |
4 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
1112 KB |
Output is correct |
| 2 |
Correct |
42 ms |
1112 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1112 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
1116 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1643 ms |
378588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
4 ms |
348 KB |
Output is correct |
| 3 |
Correct |
4 ms |
348 KB |
Output is correct |
| 4 |
Correct |
4 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
