oj.uz

Submission #340767

# Submission time Handle Problem Language Result Execution time Memory
340767 2020-12-28T10:46:58 Z talant117408 Luxury burrow (IZhO13_burrow) C++17
0 / 100
 1614 ms 26220 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], ri[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();
                }
                ri[i][k] = pos-k+1;
                st.push(mp(up[i][k], pos));
            }
            
            j = r;
        }
    }
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            mx = max(mx, (lf[i][j]+ri[i][j]-1)*up[i][j]);
        }
    }
    
    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 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 2 ms 1004 KB Output is correct
6 Correct 1 ms 1132 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 5 ms 2284 KB Output is correct
9 Correct 12 ms 4332 KB Output is correct
10 Correct 35 ms 4352 KB Output is correct
11 Correct 92 ms 5228 KB Output is correct
12 Correct 23 ms 10220 KB Output is correct
13 Correct 47 ms 2284 KB Output is correct
14 Correct 82 ms 8172 KB Output is correct
15 Correct 77 ms 8172 KB Output is correct
16 Correct 157 ms 8172 KB Output is correct
17 Correct 50 ms 10220 KB Output is correct
18 Correct 490 ms 12204 KB Output is correct
19 Correct 296 ms 14144 KB Output is correct
20 Correct 1034 ms 16236 KB Output is correct
21 Correct 1010 ms 18084 KB Output is correct
22 Incorrect 1614 ms 26220 KB Output isn't correct
23 Halted 0 ms 0 KB -