oj.uz

Submission #75980

# Submission time Handle Problem Language Result Execution time Memory
75980 2018-09-11T18:26:16 Z Vardanyan Luxury burrow (IZhO13_burrow) C++14
0 / 100
 2000 ms 21588 KB 
#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

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]);
                 ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 16124 KB Output is correct
2 Correct 20 ms 16244 KB Output is correct
3 Correct 21 ms 16280 KB Output is correct
4 Correct 27 ms 16280 KB Output is correct
5 Correct 31 ms 16408 KB Output is correct
6 Correct 23 ms 16568 KB Output is correct
7 Correct 42 ms 16568 KB Output is correct
8 Correct 118 ms 17200 KB Output is correct
9 Correct 251 ms 18124 KB Output is correct
10 Correct 1072 ms 20044 KB Output is correct
11 Correct 1810 ms 21588 KB Output is correct
12 Correct 443 ms 21588 KB Output is correct
13 Correct 1849 ms 21588 KB Output is correct
14 Execution timed out 2052 ms 21588 KB Time limit exceeded
15 Halted 0 ms 0 KB -