oj.uz

Submission #340771

# Submission time Handle Problem Language Result Execution time Memory
340771 2020-12-28T10:51:45 Z talant117408 Luxury burrow (IZhO13_burrow) C++17
0 / 100
 1682 ms 16232 KB 
/*
    Code written by Talant I.D.
*/
  
#include <bits/stdc++.h>
  
using namespace std;
  
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
  
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
  
inline bool isvowel(char ch){
    ch = tolower(ch);
    return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
  
inline bool isprime(int n){
    if(n < 2 || (n%2 == 0 && n != 2)) return false;
    for(int i = 3; i*i <= n; i++)
        if(n%i == 0) return false;
    return true;
}
 
class Union{
    private:
        vector <int> saizu, link;
    public:
        Union(int n){
            saizu.assign(n, 1); link.resize(n); 
            iota(all(link), 0);
        }
        int find(int n){
            if(link[n] == n) return n;
            return link[n] = find(link[n]);
        }
        int same(int a, int b){
            return find(a) == find(b);
        }
        void unite(int a, int b){
            if(same(a, b)) return;
             
            a = find(a); b = find(b);
            if(saizu[a] < saizu[b]) swap(a, b);
             
            saizu[a] += saizu[b];
            link[b] = a;
        }
        int getsize(int a){
            return saizu[find(a)];
        }
};
 
const int mod = 1e9+7;
 
ll mode(ll a){
    a %= mod;
    if(a < 0) a += mod;
    return a;
}
 
ll subt(ll a, ll b){
    return mode(mode(a)-mode(b));
}
 
ll add(ll a, ll b){
    return mode(mode(a)+mode(b));
}
 
ll mult(ll a, ll b){
    return mode(mode(a)*mode(b));
}
 
ll binpow(ll a, ll b){
    ll res = 1;
    while(b){
        if(b&1) res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

int n, m, acc;   
int grid[1003][1003], grid2[1003][1003], up[1003][1003], lf[1003][1003];

int check(int mid){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(grid[i][j] >= mid){
                grid2[i][j] = 1;
            }
            else{
                grid2[i][j] = 0;
            }
        }
    }
    for(int j = 1; j <= m; j++){
        for(int i = 1; i <= n; i++){
            if(!grid2[i][j]) up[i][j] = 0;
            else up[i][j] = up[i-1][j]+1;
        }
    }
    int mx = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(!grid2[i][j]) continue;
            stack <pii> st;
            int l = j, r = j+1;
            
            while(r <= m && grid2[i][r]) r++;
            r--;
            
            for(int k = l; k <= r; k++){
                int pos = k;
                while(sz(st) && st.top().first >= up[i][k]){
                    pos = st.top().second;
                    st.pop();
                }
                lf[i][k] = k-pos+1;
                st.push(mp(up[i][k], pos));
            }
            
            while(sz(st)) st.pop();
            
            for(int k = r; k >= l; k--){
                int pos = k;
                while(sz(st) && st.top().first >= up[i][k]){
                    pos = st.top().second;
                    st.pop();
                }
                mx = max(mx, (pos-k+lf[i][k])*up[i][k]);
                st.push(mp(up[i][k], pos));
            }
            
            j = r;
        }
    }
    
    return mx;
}

int main(){
    do_not_disturb
    
    cin >> n >> m >> acc;
    int mx = 0, mn = 2e9;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> grid[i][j];
            mx = max(mx, grid[i][j]);
            mn = min(mn, grid[i][j]);
        }
    }
    
    int ans = 0, area = 0;
    int l = mn, r = mx;
    while(l < r){
        int mid = (l+r+1) >> 1;
        int a = check(mid);
        if(a >= acc){
            l = mid;
            if(ans < mid){
                ans = mid;
                area = a;
            }
        }
        else{
            r = mid-1;
        }
    }
    
    cout << ans << ' ' << area;
    
    return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 2 ms 876 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 6 ms 1900 KB Output is correct
9 Correct 11 ms 3564 KB Output is correct
10 Correct 33 ms 3564 KB Output is correct
11 Correct 102 ms 4332 KB Output is correct
12 Correct 25 ms 8172 KB Output is correct
13 Correct 46 ms 1900 KB Output is correct
14 Correct 81 ms 6636 KB Output is correct
15 Correct 73 ms 6636 KB Output is correct
16 Correct 150 ms 6764 KB Output is correct
17 Correct 48 ms 8172 KB Output is correct
18 Correct 486 ms 9836 KB Output is correct
19 Correct 291 ms 11244 KB Output is correct
20 Correct 1087 ms 12980 KB Output is correct
21 Correct 1072 ms 14444 KB Output is correct
22 Incorrect 1682 ms 16232 KB Output isn't correct
23 Halted 0 ms 0 KB -