Submission #406855

#TimeUsernameProblemLanguageResultExecution timeMemory
406855ngraceRectangles (IOI19_rect)C++14
23 / 100
1946 ms856340 KiB
#include "rect.h" #include <vector> #include <iostream> #include <set> #include <stack> using namespace std; #define v vector #define pii pair<int,int> #define fi first #define se second struct gPair{ int l, u;//lower and upper vals int rc;//row or column }; long long count_rectangles(std::vector<std::vector<int> > a) { long long out=0; int R=a.size(); int C=a[0].size(); //start by getting good pairs v<gPair> rpairs; for(int r=1;r<R-1;r++){ v<int> left(C,-1); v<int> right(C,-1); stack<int> s; for(int c=0;c<C;c++){ while(s.size()>0 && a[r][s.top()]<=a[r][c]) s.pop();//go back till reach cell to left with greater than cur if(s.size()>0) left[c] = s.top();//if cell to left exists then take s.push(c); } s=stack<int>(); for(int c=C-1;c>=0;c--){ while(s.size()>0 && a[r][s.top()]<=a[r][c]) s.pop();//go forward till reach cell to right with greater than cur if(s.size()>0) right[c] = s.top();//if cell to right exists then take s.push(c); } for(int c=0;c<C;c++){ if(left[c]!=-1 && right[c]!=-1){ rpairs.push_back({left[c],right[c],r}); } } } v<gPair> cpairs; for(int c=1;c<C-1;c++){ v<int> low(R,-1); v<int> high(R,-1); stack<int> s; for(int r=0;r<R;r++){ while(s.size()>0 && a[s.top()][c]<=a[r][c]) s.pop();//go lower till reach cell lower (up) with greater than cur if(s.size()>0) low[r] = s.top();//if cell lower exists then take s.push(r); } s=stack<int>(); for(int r=R-1;r>=0;r--){ while(s.size()>0 && a[s.top()][c]<=a[r][c]) s.pop();//go higher till reach cell higher with greater than cur if(s.size()>0) high[r] = s.top();//if cell higher exists then take s.push(r); } for(int r=0;r<R;r++){ if(low[r]!=-1 && high[r]!=-1){ cpairs.push_back({low[r],high[r],c}); } } } //pairs are now initialized v<v<set<int>>> rows(R,v<set<int>>(C)); v<v<set<int>>> cols(R,v<set<int>>(C)); for(gPair g:rpairs){ //cout<<g.rc<<" "<<g.l<<" "<<g.u<<endl; cols[g.rc][g.l+1].insert(g.u-1);//the different columns ahead this cell can get to } //cout<<endl; for(gPair g:cpairs){ //cout<<g.rc<<" "<<g.l<<" "<<g.u<<endl; rows[g.l+1][g.rc].insert(g.u-1);//the differenc rows ahead this cell can get to } //check rows and cols ahead /** for(int r=0;r<R;r++){ for(int c=0;c<C;c++){ cout<<r<<" "<<c<<":"<<endl; for(int it : rows[r][c]){ cout<<it<<" "; } cout<<endl; for(int it : cols[r][c]){ cout<<it<<" "; } cout<<endl; } }**/ //now try every cell as top left: for(int r=1;r<R-1;r++){ for(int c=1;c<C-1;c++){ for(int rr:rows[r][c]){ for(int cc:cols[r][c]){ //cout<<r<<" "<<c<<" "<<rr<<" "<<cc<<endl; bool works=true; for(int x=r;x<=rr;x++){ //for each along left side check if the far col is = cc if(cols[x][c].find(cc)==cols[x][c].end()){ works=false; break; } } for(int x=c;x<=cc;x++){ //for each along left side check if the far col is = cc if(rows[r][x].find(rr)==rows[r][x].end() || !works){ works=false; break; } } if(works){ out++; } else{ break; } } } } } return out; }
#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...