Submission #1199548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199548		hyl_backup	The Kingdom of JOIOI (JOI17_joioi)	C++20	15 / 100	4094 ms	5688 KiB

joioi

//The Kingdom of JOIOI
#include <iostream>
#include <set>
#include <climits>
#include <vector>

#define MIN(a, b) ((a<b)? a :b )
#define MAX(a, b) ((a>b)? a :b )

long long h, w, min, max, col, a, b, min_a, min_b, max_a, max_b;
long long limit, ans;

long long mat[2007][2007];

std::set<std::pair<long long, long long>> set;
std::multiset<long long> og;
std::multiset<long long> ms_a;
std::multiset<long long> ms_b;
std::multiset<long long> ms_b1;

struct node{
    long long min;
    long long max;
};

node tree[207][807];

void b_tree(int pos=1, int l=0, int r=h-1){
    if(l==r){
        tree[pos][col].max=mat[l][col];
        tree[pos][col].min=mat[l][col];
        return;
    }
    int m = (l+r)/2;

    b_tree(pos*2, l, m);
    b_tree(pos*2+1, m+1, r);

    tree[pos][col].max =MAX(tree[pos*2][col].max, tree[pos*2+1][col].max);
    tree[pos][col].min =MIN(tree[pos*2][col].min, tree[pos*2+1][col].min);
}

long long min_tree(int pos = 1, int l=0, int r=h-1){
    if(l>=a && r<=b){
        return tree[pos][col].min;
    }
    int m = (l+r)/2;

    long long cat = LLONG_MAX;
    if(m<b){
        cat = MIN(cat, min_tree(pos*2+1, m+1, r));
    }
    if(m>=a){
        cat = MIN(cat, min_tree(pos*2, l, m));
    }

    return cat;
}

long long max_tree(int pos = 1, int l=0, int r=h-1){
    if(l>=a && r<=b){
        return tree[pos][col].max;
    }
    int m = (l+r)/2;

    long long cat = LLONG_MIN;
    if(m<b){
        cat = MAX(cat, max_tree(pos*2+1, m+1, r));
    }
    if(m>=a){
        cat = MAX(cat, max_tree(pos*2, l, m));
    }

    return cat;
}

std::set<std::vector<int>> dp;
std::set<std::vector<int>> dp2;

int main(){
    std::cin.tie(0);
    std::ios_base::sync_with_stdio(0);

    std::cin >> h >> w;

    for(int i = 0; i<h; ++i){
        for(int j = 0; j<w; ++j){
            std::cin >> mat[i][j];
            og.insert(mat[i][j]);
        }
    }

    min = LLONG_MAX;

    for(int j = 0; j<w; ++j){
        col=j;
        b_tree();
    }

    a = 1;
    b = 2;
    //std::cout << min_tree() << ' ' << max_tree()<<'\n';

    ans = LLONG_MAX;

    //ms_b=og;

    dp.insert({h-1, 2000123000, 0, 2000123000, 0});


    for(int j = 0; j<=w; ++j){
        for(std::vector<int> x : dp){
            //limit, min, max, min, max
            /*
            std::cout << j<<"pos ";
            for(int c : x){
                std::cout << c <<' ';
            }
            std::cout <<'\n';
            */

            limit=x[0];

            if(j==w){
                ans = MIN(ans, MAX(x[2]-x[1], x[4]-x[3]));
                continue;
            }

            col= j;
            a=0;
            b=h-1;
            dp2.insert({-1, x[1], x[2], MIN(x[3], min_tree()), MAX(x[4], max_tree())});

            min=x[1];
            max=x[2];

            for(int i = 0; i<=limit; ++i){
                min = MIN(min, mat[i][j]);
                max = MAX(max, mat[i][j]);


                a=i+1;

                dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
            }

        }
        dp.clear();
        dp=dp2;
        dp2.clear();
    }

    //std::cout << "prelim: " << ans <<'\n';

    dp.clear();

    dp.insert({-1, 2000123000, 0, 2000123000, 0});

    for(int j = 0; j<=w; ++j){
        for(std::vector<int> x : dp){
            //limit, min, max, min, max
            /*
            std::cout << j<<"pos ";
            for(int c : x){
                std::cout << c <<' ';
            }
            std::cout <<'\n';
            //*/

            limit=x[0];

            if(j==w){
                ans = MIN(ans, MAX(x[2]-x[1], x[4]-x[3]));
                continue;
            }

            col= j;
            a=0;
            b=h-1;
            //dp2.insert({-1, x[1], x[2], MIN(x[3], min_tree()), MAX(x[4], max_tree())});

            min=x[1];
            max=x[2];

            for(int i = 0; i<limit; ++i){
                min = MIN(min, mat[i][j]);
                max = MAX(max, mat[i][j]);
            }

            for(int i = limit; i<h; ++i){
                if(i>=0){
                    min = MIN(min, mat[i][j]);
                    max = MAX(max, mat[i][j]);
                }

                //std::cout <<min <<':' << max <<'\n';

                a=i+1;
                if(a<h){
                    dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
                }
                else{
                    dp2.insert({i, min, max, x[3], x[4]});
                }
            }

        }
        dp.clear();
        dp=dp2;
        dp2.clear();
    }

    std::cout << ans;

    return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:108:17: warning: narrowing conversion of '(h - 1)' from 'long long int' to 'int' [-Wnarrowing]
  108 |     dp.insert({h-1, 2000123000, 0, 2000123000, 0});
      |                ~^~
joioi.cpp:108:17: warning: narrowing conversion of '(h - 1)' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp:7:25: warning: narrowing conversion of '((((long long int)x.std::vector<int>::operator[](3)) < min_tree(1, 0, ((int)(h - 1)))) ? ((long long int)x.std::vector<int>::operator[](3)) : min_tree(1, 0, ((int)(h - 1))))' from 'long long int' to 'int' [-Wnarrowing]
    7 | #define MIN(a, b) ((a<b)? a :b )
      |                   ~~~~~~^~~~~~~~
joioi.cpp:132:41: note: in expansion of macro 'MIN'
  132 |             dp2.insert({-1, x[1], x[2], MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                         ^~~
joioi.cpp:7:25: warning: narrowing conversion of '((((long long int)x.std::vector<int>::operator[](3)) < min_tree(1, 0, ((int)(h - 1)))) ? ((long long int)x.std::vector<int>::operator[](3)) : min_tree(1, 0, ((int)(h - 1))))' from 'long long int' to 'int' [-Wnarrowing]
    7 | #define MIN(a, b) ((a<b)? a :b )
      |                   ~~~~~~^~~~~~~~
joioi.cpp:132:41: note: in expansion of macro 'MIN'
  132 |             dp2.insert({-1, x[1], x[2], MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                         ^~~
joioi.cpp:8:25: warning: narrowing conversion of '((((long long int)x.std::vector<int>::operator[](4)) > max_tree(1, 0, ((int)(h - 1)))) ? ((long long int)x.std::vector<int>::operator[](4)) : max_tree(1, 0, ((int)(h - 1))))' from 'long long int' to 'int' [-Wnarrowing]
    8 | #define MAX(a, b) ((a>b)? a :b )
      |                   ~~~~~~^~~~~~~~
joioi.cpp:132:64: note: in expansion of macro 'MAX'
  132 |             dp2.insert({-1, x[1], x[2], MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                                                ^~~
joioi.cpp:8:25: warning: narrowing conversion of '((((long long int)x.std::vector<int>::operator[](4)) > max_tree(1, 0, ((int)(h - 1)))) ? ((long long int)x.std::vector<int>::operator[](4)) : max_tree(1, 0, ((int)(h - 1))))' from 'long long int' to 'int' [-Wnarrowing]
    8 | #define MAX(a, b) ((a>b)? a :b )
      |                   ~~~~~~^~~~~~~~
joioi.cpp:132:64: note: in expansion of macro 'MAX'
  132 |             dp2.insert({-1, x[1], x[2], MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                                                ^~~
joioi.cpp:144:32: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
  144 |                 dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                ^~~
joioi.cpp:144:32: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp:144:37: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]
  144 |                 dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                     ^~~
joioi.cpp:144:37: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp:7:25: warning: narrowing conversion of '((((long long int)x.std::vector<int>::operator[](3)) < min_tree(1, 0, ((int)(h - 1)))) ? ((long long int)x.std::vector<int>::operator[](3)) : min_tree(1, 0, ((int)(h - 1))))' from 'long long int' to 'int' [-Wnarrowing]
    7 | #define MIN(a, b) ((a<b)? a :b )
      |                   ~~~~~~^~~~~~~~
joioi.cpp:144:42: note: in expansion of macro 'MIN'
  144 |                 dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                          ^~~
joioi.cpp:7:25: warning: narrowing conversion of '((((long long int)x.std::vector<int>::operator[](3)) < min_tree(1, 0, ((int)(h - 1)))) ? ((long long int)x.std::vector<int>::operator[](3)) : min_tree(1, 0, ((int)(h - 1))))' from 'long long int' to 'int' [-Wnarrowing]
    7 | #define MIN(a, b) ((a<b)? a :b )
      |                   ~~~~~~^~~~~~~~
joioi.cpp:144:42: note: in expansion of macro 'MIN'
  144 |                 dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                          ^~~
joioi.cpp:8:25: warning: narrowing conversion of '((((long long int)x.std::vector<int>::operator[](4)) > max_tree(1, 0, ((int)(h - 1)))) ? ((long long int)x.std::vector<int>::operator[](4)) : max_tree(1, 0, ((int)(h - 1))))' from 'long long int' to 'int' [-Wnarrowing]
    8 | #define MAX(a, b) ((a>b)? a :b )
      |                   ~~~~~~^~~~~~~~
joioi.cpp:144:65: note: in expansion of macro 'MAX'
  144 |                 dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                                                 ^~~
joioi.cpp:8:25: warning: narrowing conversion of '((((long long int)x.std::vector<int>::operator[](4)) > max_tree(1, 0, ((int)(h - 1)))) ? ((long long int)x.std::vector<int>::operator[](4)) : max_tree(1, 0, ((int)(h - 1))))' from 'long long int' to 'int' [-Wnarrowing]
    8 | #define MAX(a, b) ((a>b)? a :b )
      |                   ~~~~~~^~~~~~~~
joioi.cpp:144:65: note: in expansion of macro 'MAX'
  144 |                 dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                                                 ^~~
joioi.cpp:200:36: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
  200 |                     dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                    ^~~
joioi.cpp:200:36: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp:200:41: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]
  200 |                     dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                         ^~~
joioi.cpp:200:41: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp:7:25: warning: narrowing conversion of '((((long long int)x.std::vector<int>::operator[](3)) < min_tree(1, 0, ((int)(h - 1)))) ? ((long long int)x.std::vector<int>::operator[](3)) : min_tree(1, 0, ((int)(h - 1))))' from 'long long int' to 'int' [-Wnarrowing]
    7 | #define MIN(a, b) ((a<b)? a :b )
      |                   ~~~~~~^~~~~~~~
joioi.cpp:200:46: note: in expansion of macro 'MIN'
  200 |                     dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                              ^~~
joioi.cpp:7:25: warning: narrowing conversion of '((((long long int)x.std::vector<int>::operator[](3)) < min_tree(1, 0, ((int)(h - 1)))) ? ((long long int)x.std::vector<int>::operator[](3)) : min_tree(1, 0, ((int)(h - 1))))' from 'long long int' to 'int' [-Wnarrowing]
    7 | #define MIN(a, b) ((a<b)? a :b )
      |                   ~~~~~~^~~~~~~~
joioi.cpp:200:46: note: in expansion of macro 'MIN'
  200 |                     dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                              ^~~
joioi.cpp:8:25: warning: narrowing conversion of '((((long long int)x.std::vector<int>::operator[](4)) > max_tree(1, 0, ((int)(h - 1)))) ? ((long long int)x.std::vector<int>::operator[](4)) : max_tree(1, 0, ((int)(h - 1))))' from 'long long int' to 'int' [-Wnarrowing]
    8 | #define MAX(a, b) ((a>b)? a :b )
      |                   ~~~~~~^~~~~~~~
joioi.cpp:200:69: note: in expansion of macro 'MAX'
  200 |                     dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                                                     ^~~
joioi.cpp:8:25: warning: narrowing conversion of '((((long long int)x.std::vector<int>::operator[](4)) > max_tree(1, 0, ((int)(h - 1)))) ? ((long long int)x.std::vector<int>::operator[](4)) : max_tree(1, 0, ((int)(h - 1))))' from 'long long int' to 'int' [-Wnarrowing]
    8 | #define MAX(a, b) ((a>b)? a :b )
      |                   ~~~~~~^~~~~~~~
joioi.cpp:200:69: note: in expansion of macro 'MAX'
  200 |                     dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                                                     ^~~
joioi.cpp:203:36: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
  203 |                     dp2.insert({i, min, max, x[3], x[4]});
      |                                    ^~~
joioi.cpp:203:36: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp:203:41: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]
  203 |                     dp2.insert({i, min, max, x[3], x[4]});
      |                                         ^~~
joioi.cpp:203:41: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]

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