Submission #1125559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125559		AverageAmogusEnjoyer	The Kingdom of JOIOI (JOI17_joioi)	C++20	0 / 100	70 ms	94532 KiB

joioi

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> ui(0, 1 << 30);

int rng() { 
    return ui(mrand);
}

const int N=2001;
int grid[N][N];
int vals[N*N];
vector<pair<int,int>> pos[N*N];
int n,m;
int diff;
int Min[N][N],Max[N][N];
int suffMin[N*N];

bool can(int mid) {
    int p=0;
    int curr_min=1<<30,curr_max=0;
    for (int i=0;i<diff;i++) {
        // this is the 'lower' max
        // cout << "I'm saying " << vals[i] << " is the current max " << endl;
        while(vals[i]-vals[p]>mid) {
            for (auto &[x,y]: pos[p]) {
                // cout << "therefore I gotta erase pos " << x << ", " << y << " with value " << grid[x][y] << endl;
                cmin(curr_min,Min[x][y]),cmax(curr_max,Max[x][y]);
            }
            p++;
        }
        // cout << "which leads to Min = " << curr_min << ", Max = " << curr_max << endl;
        if ((i + 1 == diff ? curr_max:vals[diff-1]) - min(suffMin[i+1],curr_min) <= mid)
            return 1;
    }
    return 0;
}

int work() {
    int lo=0,hi=1<<30;
    while(lo<hi) {
        int mid=lo+(hi-lo)/2;
        if (can(mid)) 
            hi=mid;
        else    
            lo=mid+1;
    }
    return lo;
}

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);
    
    cin >> n >> m;
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++) {
            cin >> grid[i][j];
            vals[m*i+j]=grid[i][j];
        }
    sort(vals,vals+n*m);
    diff=unique(vals,vals+n*m)-vals;
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
            pos[lower_bound(vals,vals+diff,grid[i][j])-vals].emplace_back(i,j);
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
            Max[i][j]=Min[i][j]=grid[i][j];
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++) {
            if (i > 0)
                cmax(Max[i][j],Max[i-1][j]);
            if (j > 0)
                cmax(Max[i][j],Max[i][j-1]);
            if (i > 0)
                cmin(Min[i][j],Min[i-1][j]);
            if (j > 0)
                cmin(Min[i][j],Min[i][j-1]);
        }

    suffMin[diff]=1<<30;
    for (int i=diff-1;i>=0;i--) {
        suffMin[i]=suffMin[i+1];
        for (auto &[x,y]: pos[i]) {
            cmin(suffMin[i],Min[x][y]);
        }
    }
    int ans=work();

    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
            Max[i][j]=Min[i][j]=grid[i][j];
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++) {
            if (i + 1 < n)
                cmax(Max[i][j],Max[i+1][j]);
            if (j + 1 < m)
                cmax(Max[i][j],Max[i][j+1]);
            if (i + 1 < n)
                cmin(Min[i][j],Min[i+1][j]);
            if (j + 1 < m)
                cmin(Min[i][j],Min[i][j+1]);
        }

    suffMin[diff]=1<<30;
    for (int i=diff-1;i>=0;i--) {
        suffMin[i]=suffMin[i+1];
        for (auto &[x,y]: pos[i]) {
            cmin(suffMin[i],Min[x][y]);
        }
    }
    int ans2=work();
    cout << min(ans,ans2) << "\n";
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40