Submission #410000

#TimeUsernameProblemLanguageResultExecution timeMemory
410000rumen_mRectangles (IOI19_rect)C++17
0 / 100
847 ms1048580 KiB
#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,n,a.x1,a.x2)<=a.y2-a.y1)return false; if(l[a.x2+1].query(1,0,n,a.x1,a.x2)<=a.y2-a.y1)return false; if(u[a.y1-1].query(1,0,m,a.y1,a.y2)<=a.x2-a.x1)return false; if(d[a.y2+1].query(1,0,m,a.y1,a.y2)<=a.x2-a.x1)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,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=0;i<=n-1;i++) for(j=0;j<=m-1;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 (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:157:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for(i=0;i<f.size();i++)
      |             ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...