oj.uz

Submission #75993

# Submission time Handle Problem Language Result Execution time Memory
75993 2018-09-11T18:55:53 Z Vardanyan Luxury burrow (IZhO13_burrow) C++14
0 / 100
 2000 ms 4968 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int t[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[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[v] = min(t[v*2],t[v*2+1]);
}
int query(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[v];
    int m = (s+e)/2;
    return min(query(v*2,s,m,l,min(m,r)),query(v*2+1,m+1,e,max(l,m+1),r));
}
int n,m,k;
int get(int x){
  //  cout<<x<<endl;
    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));
        memset(t,0,sizeof(t));
        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(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(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 2 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 712 KB Output is correct
4 Correct 4 ms 712 KB Output is correct
5 Correct 7 ms 784 KB Output is correct
6 Correct 14 ms 784 KB Output is correct
7 Correct 17 ms 784 KB Output is correct
8 Correct 155 ms 1552 KB Output is correct
9 Correct 358 ms 2332 KB Output is correct
10 Correct 1002 ms 2512 KB Output is correct
11 Correct 1635 ms 3044 KB Output is correct
12 Correct 832 ms 4968 KB Output is correct
13 Correct 1728 ms 4968 KB Output is correct
14 Execution timed out 2045 ms 4968 KB Time limit exceeded
15 Halted 0 ms 0 KB -