Submission #422886

#TimeUsernameProblemLanguageResultExecution timeMemory
422886oleh1421Rectangles (IOI19_rect)C++17
Compilation error
0 ms0 KiB
#include "grader.cpp" #include "rect.h" #include<bits/stdc++.h> typedef long long ll; using namespace std; int n,m; const int N=2500; int a[N][N],l[N][N],r[N][N]; int mx[N]; int L[N],R[N]; int x[N],y[N]; vector<int>Q[N]; int t[N]; void upd(int n,int pos,int x){ for (;pos<=n;pos|=pos+1) t[pos]+=x; } int get(int pos){ int sum=0; for (;pos>=0;pos&=pos+1,pos--) sum+=t[pos]; return sum; } int Cnt[N]; ll count_rectangles(vector<vector<int> > vv) { n=vv.size(),m=vv[0].size(); for (int i=1;i<=n;i++){ for (int j=1;j<=m;j++){ a[i][j]=vv[i-1][j-1]; } } for (int i=1;i<=n;i++){ for (int j=1;j<=m;j++){ l[i][j]=0; for (int t=j-1;t>=1;t=l[i][t]){ if (a[i][t]>=a[i][j]){ l[i][j]=t; break; } } } for (int j=m;j>=1;j--){ r[i][j]=m+1; for (int t=j+1;t<=m;t=r[i][t]){ if (a[i][t]>=a[i][j]){ r[i][j]=t; break; } } } } ll res=0ll; for (int i=1;i<=n;i++){ for (int j=1;j<=m;j++) mx[j]=0,L[j]=1,R[j]=m; for (int j=i+2;j<=n;j++){ for (int t=1;t<=m;t++) { mx[t]=max(mx[t],a[j-1][t]); L[t]=max(L[t],l[j-1][t]); R[t]=min(R[t],r[j-1][t]); } vector<int>bad; bad.push_back(0); for (int t=1;t<=m;t++){ if (mx[t]>=min(a[i][t],a[j][t])) bad.push_back(t); } bad.push_back(m+1); for (int t=1;t<bad.size();t++){ for (int k=bad[t-1];k<bad[t];k++){ y[k]=min(R[k],bad[t]); } for (int k=bad[t-1]+1;k<=bad[t];k++){ x[k]=max(L[k],bad[t-1]); } } for (int t=1;t<=m;t++) Q[x[t]].push_back(t); for (int k=1;k<=m;k++) t[k]=0,Cnt[k]=0; for (int t=1;t<=m;t++){ for (int k:Q[t]){ upd(m,k,1); Cnt[k]++; } if (y[t]>=t+2) res+=get(y[t])-get(t+1); } for (int t=1;t<=m;t++) Q[t].clear(); } } return res; } /** 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 5 13 5 6 **/

Compilation message (stderr)

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:65:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             for (int t=1;t<bad.size();t++){
      |                          ~^~~~~~~~~~~
/usr/bin/ld: /tmp/ccCVXNhT.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccjPUcnV.o:rect.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status