Submission #1125564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125564		AverageAmogusEnjoyer	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	2796 ms	110076 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 MinPos[N*N],MaxPos[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) {
            cmin(curr_min,MinPos[p]),cmax(curr_max,MaxPos[p]);
            // for (auto &[x,y]: pos[p]) {
                // 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 get(int v) {
    return lower_bound(vals,vals+diff,v)-vals;
}

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++)
            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]);
        }


    memset(MinPos,0x3f,sizeof(MinPos));
    memset(MaxPos,0,sizeof(MaxPos));
    for (int i=0;i<n;i++) 
        for (int j=0;j<m;j++) {
            int v = get(grid[i][j]);
            cmin(MinPos[v],Min[i][j]),cmax(MaxPos[v],Max[i][j]);
        }
    suffMin[diff]=1<<30;
    for (int i=diff-1;i>=0;i--) {
        suffMin[i]=min(suffMin[i+1],MinPos[i]);
        // 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=m-1;j>=0;j--) {
            if (i > 0)
                cmax(Max[i][j],Max[i-1][j]);
            if (j + 1 < m)
                cmax(Max[i][j],Max[i][j+1]);
            if (i > 0)
                cmin(Min[i][j],Min[i-1][j]);
            if (j + 1 < m)
                cmin(Min[i][j],Min[i][j+1]);
        }

    memset(MinPos,0x3f,sizeof(MinPos));
    memset(MaxPos,0,sizeof(MaxPos));
    for (int i=0;i<n;i++) 
        for (int j=0;j<m;j++) {
            int v = get(grid[i][j]);
            cmin(MinPos[v],Min[i][j]),cmax(MaxPos[v],Max[i][j]);
        }
    suffMin[diff]=1<<30;
    for (int i=diff-1;i>=0;i--) {
        suffMin[i]=min(suffMin[i+1],MinPos[i]);
        // for (auto &[x,y]: pos[i]) {
            // cmin(suffMin[i],Min[x][y]);
        // }
    }
    int ans2=work();
    cout << min(ans,ans2) << "\n";
}

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