Submission #669717

#	Time	Username	Problem	Language	Result	Execution time	Memory
669717		Darren0724	The Kingdom of JOIOI (JOI17_joioi)	C++17	0 / 100	2 ms	212 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
#define x first
#define y second
const int INF=1e9;
int n,m;
vector<vector<int>> v;
vector<vector<int>> premin,premax;
vector<vector<int>> sufmin,sufmax;
bool check1(int r,int l){
    cout<<r<<' '<<l<<endl;
    vector<int> a(n+1),b(n+1);
    for(int i=1;i<=n;i++){
        a[i]=upper_bound(all(premax[i]),r)-premax[i].begin()-1;
    }
    for(int i=1;i<=n;i++){
        b[i]=lower_bound(all(sufmin[i]),l)-sufmin[i].begin();
    }
    for(int i=2;i<=n;i++){
        a[i]=min(a[i],a[i-1]);
    }
    for(int i=n-1;i>0;i--){
        b[i]=max(b[i],b[i+1]);
    }
    for(int i=1;i<=n;i++){
        cout<<a[i]<<' ';
    }
    cout<<endl;
    for(int i=1;i<=n;i++){
        cout<<b[i]<<' ';
    }
    cout<<endl;
    bool flag=1;
    for(int i=1;i<=n;i++){
        if(b[i]-a[i]>1){
            flag=0;
        }
    }
    return flag;
}
bool check2(int l,int r){
    cout<<l<<' '<<r<<endl;
    vector<int> a(n+1),b(n+1);
    for(int i=1;i<=n;i++){
        a[i]=upper_bound(all(premin[i]),l,greater<int>())-premin[i].begin()-1;
    }
    for(int i=1;i<=n;i++){
        b[i]=lower_bound(all(sufmax[i]),r,greater<int>())-sufmax[i].begin();
    }
    for(int i=2;i<=n;i++){
        a[i]=min(a[i],a[i-1]);
    }
    for(int i=n-1;i>0;i--){
        b[i]=max(b[i],b[i+1]);
    }
    for(int i=1;i<=n;i++){
        cout<<a[i]<<' ';
    }
    cout<<endl;
    for(int i=1;i<=n;i++){
        cout<<b[i]<<' ';
    }
    cout<<endl;
    bool flag=1;
    for(int i=1;i<=n;i++){
        if(b[i]-a[i]>1){
            flag=0;
        }
    }
    return flag;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    v.resize(n+2,vector<int>(m+2));
    premin.resize(n+2,vector<int>(m+2,INF));
    premax.resize(n+2,vector<int>(m+2));
    sufmin.resize(n+2,vector<int>(m+2,INF));
    sufmax.resize(n+2,vector<int>(m+2));
    int mx=-INF,mn=INF;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>v[i][j];
            premax[i][j]=max(premax[i][j-1],v[i][j]);
            premin[i][j]=min(premin[i][j-1],v[i][j]);
            mn=min(mn,v[i][j]);
            mx=max(mx,v[i][j]);
        }
        premin[i][m+1]=-INF;
        premax[i][m+1]=INF;
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=1;j--){
            sufmin[i][j]=min(sufmin[i][j+1],v[i][j]);
            sufmax[i][j]=max(sufmax[i][j+1],v[i][j]);
        }
        sufmin[i][0]=-INF;
        sufmax[i][0]=INF;
        sufmin[i][m+1]=INF;
        sufmax[i][m+1]=-INF;
    }
    cout<<mn<<' '<<mx<<endl;
    int ans=INF;
    int l=-1,r=mx-mn+1;
    while(r-l>1){
        int m=(l+r)>>1;
        if(check1(mn+m,mx-m)){
            r=m;
        }
        else{
            l=m;
        }
    }
    cout<<"------"<<endl;
    ans=min(ans,r);
    l=-1,r=mx-mn+1;
    while(r-l>1){
        int m=(l+r)>>1;
        if(check2(mx-m,mn+m)==1){
            r=m;
        }
        else{
            l=m;
        }
    }
    ans=min(ans,r);
    cout<<ans<<endl;

    return 0;
}

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