| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 410015 |
2021-05-21T21:10:32 Z |
rumen_m |
Rectangles (IOI19_rect) |
C++17 |
|
61 ms |
98732 KB |
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2505;
struct segment
{
int segm[maxn];
segment ()
{
int i;
for(i=0;i<maxn;i++)
segm[i] = 1e9;
}
void update(int v, int l, int r, int x, int delta)
{
if(l==r)
{
if(delta!=0)
segm[v] = delta;
return ;
}
int mid = (l+r)/2;
if(x<=mid)update(2*v,l,mid,x,delta);
else
update(2*v+1,mid+1,r,x,delta);
segm[v] = min(segm[2*v],segm[2*v+1]);
}
int query(int v, int from, int to, int l, int r)
{
if(l<=from&&to<=r)return segm[v];
int mid = (from+to)/2;
int ans = 1e9;
if(l<=mid)ans = query(2*v,from,mid,l,r);
if(r>mid)ans = min(ans,query(2*v+1,mid+1,to,l,r));
return ans;
}
};
segment l[maxn],r[maxn],d[maxn],u[maxn];
vector<vector<int> > a;
stack <int> k,empt;
struct rect
{
int x1,x2,y1,y2;
};
rect b[maxn][maxn];
vector <rect> f;
rect S;
int p[maxn];
bool cmp(rect i, rect j)
{
if(i.x1==j.x1)
{
if(i.y1==j.y1)
{
if(i.x2==j.x2)
return i.y2<j.y2;
return i.x2<j.x2;
}
return i.y1<j.y1;
}
return i.x1<j.x1;
}
int ANS = 0;
int n,m;
bool check(rect a)
{
//cout<<"CHECK: "<<a.x1<<" "<<a.y1<<" : "<<a.x2<<" "<<a.y2<<" || "<<r[a.x1-1].query(1,0,m,a.x1,a.x2)<<" "<<l[a.x2+1].query(1,0,m,a.x1,a.x2)<<" "<<u[a.y1-1].query(1,0,n,a.y1,a.y2)<<" "<<d[a.y2+1].query(1,0,n,a.y1,a.y2)<<endl;
if(r[a.x1-1].query(1,0,m,a.x1,a.x2)<=a.y2-a.y1+1)return false;
if(l[a.x2+1].query(1,0,m,a.x1,a.x2)<=a.y2-a.y1+1)return false;
if(u[a.y1-1].query(1,0,n,a.y1,a.y2)<=a.x2-a.x1+1)return false;
if(d[a.y2+1].query(1,0,n,a.y1,a.y2)<=a.x2-a.x1+1)return false;
// cout<<"YES"<<endl;
return true;
}
long long count_rectangles(std::vector<std::vector<int> > _a) {
a = _a;
int i,j;
n = a.size();
m = a[0].size();
for(i=0;i<=n-1;i++)
{
k = empt;
// k.push(0);
for(j=0;j<=m-1;j++)
{
while(!k.empty()&&a[i][j]>=a[i][k.top()])k.pop();
if(!k.empty()) b[i][j].x1 = j-k.top();
else
b[i][j].x1 = 0;
l[j].update(1,0,m,i,b[i][j].x1);
k.push(j);
}
}
for(i=0;i<=n-1;i++)
{
k = empt;
//k.push(m-1);
for(j=m-1;j>=0;j--)
{
while(!k.empty()&&a[i][j]>=a[i][k.top()])k.pop();
if(!k.empty()) b[i][j].x2 = k.top()-j;
else
b[i][j].x2 = 0;
r[j].update(1,0,m,i,b[i][j].x2);
k.push(j);
}
}
for(i=0;i<=m-1;i++)
{
k = empt;
//k.push(0);
for(j=0;j<=n-1;j++)
{
while(!k.empty()&&a[j][i]>=a[k.top()][i])k.pop();
if(!k.empty()) b[j][i].y1 = j-k.top();
else
b[j][i].y1 = 0;
u[j].update(1,0,n,i,b[j][i].y1);
k.push(j);
}
}
for(i=0;i<=m-1;i++)
{
k = empt;
//k.push(n-1);
for(j=n-1;j>=0;j--)
{
while(!k.empty()&&a[j][i]>=a[k.top()][i])k.pop();
if(!k.empty()) b[j][i].y2 = k.top()-j;
else
b[j][i].y2 = 0;
d[j].update(1,0,n,i,b[j][i].y2);
k.push(j);
}
}
////////////////////////////
for(i=0;i<=n-1;i++)
{
k = empt;
// k.push(0);
for(j=0;j<=m-1;j++)
{
while(!k.empty()&&a[i][j]>a[i][k.top()])k.pop();
if(!k.empty()) b[i][j].x1 = j-k.top();
else
b[i][j].x1 = 0;
// l[j].update(1,0,n,i,b[i][j].x1);
k.push(j);
}
}
for(i=0;i<=n-1;i++)
{
k = empt;
//k.push(m-1);
for(j=m-1;j>=0;j--)
{
while(!k.empty()&&a[i][j]>a[i][k.top()])k.pop();
if(!k.empty()) b[i][j].x2 = k.top()-j;
else
b[i][j].x2 = 0;
// r[j].update(1,0,n,i,b[i][j].x2);
k.push(j);
}
}
for(i=0;i<=m-1;i++)
{
k = empt;
//k.push(0);
for(j=0;j<=n-1;j++)
{
while(!k.empty()&&a[j][i]>a[k.top()][i])k.pop();
if(!k.empty()) b[j][i].y1 = j-k.top();
else
b[j][i].y1 = 0;
// u[j].update(1,0,m,i,b[j][i].y1);
k.push(j);
}
}
for(i=0;i<=m-1;i++)
{
k = empt;
//k.push(n-1);
for(j=n-1;j>=0;j--)
{
while(!k.empty()&&a[j][i]>a[k.top()][i])k.pop();
if(!k.empty()) b[j][i].y2 = k.top()-j;
else
b[j][i].y2 = 0;
// d[j].update(1,0,m,i,b[j][i].y2);
k.push(j);
}
}
for(i=1;i<=n-2;i++)
for(j=1;j<=m-2;j++)
{
// cout<<i<<" "<<j<<"-> "<<b[i][j].x1<<" "<<b[i][j].x2<<" "<<b[i][j].y1<<" "<<b[i][j].y2<<endl;
if(b[i][j].x1==0||b[i][j].x2==0||b[i][j].y1==0||b[i][j].y2==0)continue;
S.x1 = j - b[i][j].x1+1;
S.x2 = j + b[i][j].x2-1;
S.y1 = i - b[i][j].y1+1;
S.y2 = i + b[i][j].y2-1;
f.push_back(S);
}
sort(f.begin(),f.end(),cmp);
for(i=0;i<f.size();i++)
{
if(i>0)
{
if(f[i-1].x1==f[i].x1&&f[i-1].x2==f[i].x2&&f[i-1].y1==f[i].y1&&f[i-1].y2==f[i].y2)
continue;
}
ANS+= check(f[i]);
}
return ANS;
}
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 8 7 5 6
*/
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:223:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
223 | for(i=0;i<f.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
98500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
98500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
98500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
98500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
61 ms |
98732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
98496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
98500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
