Submission #29415

#	Time	Username	Problem	Language	Result	Execution time	Memory
29415		osmanorhan	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	3356 ms	91796 KiB

joioi

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <list>
#include <climits>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cassert>
#include <vector>
#define all(x) x.begin() , x.end()
#define fi first
#define se second
#define pb push_back
#define umax( x , y ) x = max( x , (y) )
#define umin( x , y ) x = min( x , (y) )
#define For( i , a ) for(int i=1;i<=a;i++)
#define ort (b+s)/2
#define y2 asrwjaelkf
#define y1 asseopirwjaelkf

using namespace std;

const int maxn = 2020;
const int kokn = 390;
const int MOd = 1e9+7;

typedef long long Lint;
typedef long double db;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;

int a, b;

struct fenwick{
    int fw[maxn];
    int v = 0;
    void clear() {
        for(int i=1;i<=max(a,b);i++) fw[i] = 0;
    }
    void up( int x, int y ) {
        if( v ) {
            x = b - x + 1;
            y = a - y + 1;
        }
        for(int i=x;i>0;i-=i&(-i)) umax( fw[i], y );
    }
    int find( int x ) {
        if( v ) {
            x = b - x + 1;
        }
        int t = 0;
        for(int i=x;i<=b;i+=i&(-i)) umax( t, fw[i] );
        return t;
    }

}l, r;

int ar[maxn][maxn];
vector<iii> v;
int fw[maxn], maxi, mini;

void rot() {
    for(int i=0;i<v.size();i++) {
        v[i].se = ii( b-v[i].se.se+1, v[i].se.fi );
        ar[v[i].se.fi][v[i].se.se] = v[i].fi;
    }
    swap( a, b );
}

void print() {
    printf("------------ %d %d\n",a,b);
    for(int i=1;i<=a;i++,printf("\n"))
        for(int j=1;j<=b;j++) printf("%d ",ar[i][j]);
}

int calc() {
    l.clear();
    r.clear();
    int lo = 0, loc = 1;
    int hi = 1e9, hic = 1;
    int i=0,j=v.size()-1;
    while( i <= j ) {
        if( loc && maxi - v[i].fi >= v[j].fi-mini ) {
            int x = v[i].se.fi;
            int y = v[i].se.se;
            int vv = r.find( y );
            if( x+vv > a ) {
                //printf("asd vi=%d vj=%d vv = %d-- %d %d\n",v[i].fi,v[j].fi,vv,x,y);
                loc = 0;
                continue;
            }
            l.up( y, x );
            i++;
        } else if( hic ) {
            int x = v[j].se.fi;
            int y = v[j].se.se;
            int v = l.find( y );
            if( x <= v ) {
                hic = 0;
                continue;
            }
            //printf("added %d %d\n",x,y);
            r.up( y, x );
            j--;
        } else break;
    }
    return max( maxi-v[i].fi, v[j].fi-mini );
}

int main()
{
    //freopen("asd.in","r",stdin);

    scanf("%d %d",&a,&b);

    for(int i=1;i<=a;i++)
        for(int j=1;j<=b;j++)
            scanf("%d",&ar[i][j]), v.pb( iii( ar[i][j], ii( i, j )) );
    r.v = 1;
    sort( all( v ) );
    maxi = v[v.size()-1].fi;
    mini = v[0].fi;
    int ans = 1e9;
    //rot();
    for(int i=0;i<4;i++) {
        //printf("asd %d\n",i);
        //print();
        umin( ans, calc(  ) );
        rot();
    }
    cout << ans << endl;
}

Compilation message (stderr)

joioi.cpp: In function 'void rot()':
joioi.cpp:69:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v.size();i++) {
                  ^
joioi.cpp: In function 'int calc()':
joioi.cpp:85:9: warning: unused variable 'lo' [-Wunused-variable]
     int lo = 0, loc = 1;
         ^
joioi.cpp:86:9: warning: unused variable 'hi' [-Wunused-variable]
     int hi = 1e9, hic = 1;
         ^
joioi.cpp: In function 'int main()':
joioi.cpp:120:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&a,&b);
                         ^
joioi.cpp:124:70: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&ar[i][j]), v.pb( iii( ar[i][j], ii( i, j )) );
                                                                      ^

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