Submission #75980

#TimeUsernameProblemLanguageResultExecution timeMemory
75980VardanyanLuxury burrow (IZhO13_burrow)C++14
0 / 100
2052 ms21588 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1005; int t[N][4*N]; int b[N][N]; int a[N][N]; int L[N]; int R[N]; void build(int row,int v,int l,int r){ if(l == r){ t[row][v] = a[row][l]; return; } int m = (l+r)/2; build(row,v*2,l,m); build(row,v*2+1,m+1,r); t[row][v] = min(t[row][v*2],t[row][v*2+1]); } int query(int row,int v,int s,int e,int l,int r){ if(l>r) return 1000*1000*1000+5; if(s == l && e == r) return t[row][v]; int m = (s+e)/2; return min(query(row,v*2,s,m,l,min(m,r)),query(row,v*2+1,m+1,e,max(l,m+1),r)); } int n,m,k; int get(int x){ // cout<<x<<endl; memset(t,0,sizeof(t)); int mxs = 0; for(int i = 1;i<=n;i++){ for(int j = 1;j<=m;j++){ if(b[i][j] >= x) a[i][j] = a[i-1][j]+1; else a[i][j] = 0; } } for(int i = 1;i<=n;i++){ memset(L,0,sizeof(L)); memset(R,0,sizeof(R)); build(i,1,1,m); for(int j = 1;j<=m;j++){ int u = a[i][j]; int l = j,r = j; int lans = l,rans = r; int lo = j,hi = m; while(lo<=hi){ int mid = (lo+hi)/2; // cout<<j<<" "<<mid<<endl; int mn = query(i,1,1,m,j,mid); if(mn>=u){ rans = mid; lo = mid+1; } else hi = mid-1; } lo = 1; hi = j; while(lo<=hi){ int mid = (lo+hi)/2; int mn = query(i,1,1,m,mid,j); if(mn>=u){ lans = mid; hi = mid-1; } else lo = mid+1; } u*=(rans-lans+1); mxs = max(mxs,u); L[j] = l; R[j] = r; } } return mxs; } int main(){ scanf("%d%d%d",&n,&m,&k); vector<int> all; map<int,int> mp; for(int i = 1;i<=n;i++){ for(int j = 1;j<=m;j++){ scanf("%d",&b[i][j]); if(!mp[b[i][j]]){ all.push_back(b[i][j]); mp[b[i][j]] = 1; } } } sort(all.begin(),all.end()); int l = 0; int r = all.size()-1; int ans = 0; int mxs = k; while(l<=r){ int m = (l+r)/2; int y = get(all[m]); if(y>=k){ ans = m; mxs = y; l = m+1; } else r = m-1; } cout<<all[ans]<<" "<<mxs<<endl; return 0; }

Compilation message (stderr)

burrow.cpp: In function 'int main()':
burrow.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&m,&k);
     ~~~~~^~~~~~~~~~~~~~~~~~~
burrow.cpp:82:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d",&b[i][j]);
                 ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...