Submission #1046143

#TimeUsernameProblemLanguageResultExecution timeMemory
1046143boyliguanhanRectangles (IOI19_rect)C++17
100 / 100
4785 ms928100 KiB
#include "rect.h" #include<bits/stdc++.h> using namespace std; #pragma GCC optimize(3) #define all(x) x.begin(),x.end() #define HAS(a,b) (lower_bound(all(a),b)!=upper_bound(all(a),b)) vector<int>pos[2501][2501],pos2[2501][2501],stb[2501][20]; vector<int> operator & (const vector<int>&a,const vector<int>&b){ vector<int>c; if(a.size()<b.size()){ for(auto i:a) if(HAS(b,i)) c.push_back(i); } else for(auto i:b) if(HAS(a,i)) c.push_back(i); return c; } vector<array<int,4>> ops; int CC; vector<int>res; int calc(int r1,int r2,int beg){ for(int i=20;i--;) if(HAS(stb[beg][i],r2)) beg+=1<<i; return beg-1; } int cnt(int l,int r,int col){ int x=31-__builtin_clz(r-l+1); vector<int>k=stb[l][x]&stb[r-(1<<x)+1][x]; return upper_bound(k.begin(),k.end(),res[CC++])-k.begin(); } long long count_rectangles(std::vector<std::vector<int> > a) { int n=a.size(),m=a[0].size(); int ans=0; for(int i=1;i<n-1;i++){ stack<int>stk; stk.push(m-1); for(int j=m-1;j--;){ while(stk.size()&&a[i][j]>a[i][stk.top()]) pos[i][j+1].push_back(stk.top()-1),stk.pop(); if(stk.size()){ pos[i][j+1].push_back(stk.top()-1); if(a[i][stk.top()]==a[i][j]) stk.pop(); } stk.push(j); if(pos[i][j+1].size()) pos[i][j+1].erase(pos[i][j+1].begin()); } } for(int j=1;j<m-1;j++){ stack<int>stk; stk.push(n-1); for(int i=n-1;i--;){ while(stk.size()&&a[i][j]>a[stk.top()][j]) pos2[i+1][j].push_back(stk.top()-1),stk.pop(); if(stk.size()){ pos2[i+1][j].push_back(stk.top()-1); if(a[stk.top()][j]==a[i][j]) stk.pop(); } stk.push(i); if(pos2[i+1][j].size()) pos2[i+1][j].erase(pos2[i+1][j].begin()); } } for(int j=1;j<m-1;j++) for(int i=1;i<n-1;i++) for(auto x:pos2[i][j]) ops.push_back({i,x,j,CC++}); res.resize(CC); CC=0; sort(ops.begin(),ops.end()); int currr=0; for(auto[r1,r2,col,id]:ops){ if(r1-currr) { currr=r1; for(int i=1;i<m-1;i++) stb[i][0]=pos2[r1][i]; for(int j=1;j<20;j++) for(int i=1;i+(1<<j)<m;i++) stb[i][j]=stb[i][j-1]&stb[i+(1<<j-1)][j-1]; } res[id]=calc(r1,r2,col); } ops.clear(); for(int col=1;col<m-1;col++){ for(int i=1;i<n-1;i++) stb[i][0]=pos[i][col]; for(int j=1;j<20;j++) for(int i=1;i+(1<<j)<n;i++) stb[i][j]=stb[i][j-1]&stb[i+(1<<j-1)][j-1]; for(int row1=1;row1<n-1;row1++) for(auto row2:pos2[row1][col]) ans+=cnt(row1,row2,col); } return ans; }

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:82:50: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   82 |                 stb[i][j]=stb[i][j-1]&stb[i+(1<<j-1)][j-1];
      |                                                 ~^~
rect.cpp:91:46: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   91 |             stb[i][j]=stb[i][j-1]&stb[i+(1<<j-1)][j-1];
      |                                             ~^~
#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...