Submission #995050

#	Time	Username	Problem	Language	Result	Execution time	Memory
995050		_callmelucian	The Kingdom of JOIOI (JOI17_joioi)	C++14	60 / 100	801 ms	262144 KiB

joioi

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

vector<int> cmp;

int getID (int targ) {
    return lower_bound(all(cmp), targ) - cmp.begin();
}

const int mn = 4e6 + 6;
int lo[2002][2002], hi[2002][2002], loCol[2002][2002], hiCol[2002][2002];
int calcLo[mn], calcHi[mn], bound[2002];
vector<pii> contain[mn];

bool ok (int i, int j) {
    return j < bound[i];
}

bool check (int delta) {
    int pos = -1, curLo = INT_MAX, curHi = INT_MIN;
    for (int k = 0; k < cmp.size(); k++) {
        while (pos + 1 < cmp.size() && cmp[pos + 1] < cmp[k] - delta) {
            pos++;
            for (auto [row, col] : contain[pos]) {
                curLo = min(curLo, lo[row][col]);
                curHi = max(curHi, hi[row][col]);
            }
        }
        int cHi = max(calcHi[k], curHi);
        int cLo = min(calcLo[k], curLo);
        if (cHi != INT_MIN && cLo != INT_MAX && cHi - cLo <= delta) return 1;
    }
    return 0;
}

int solve (vector<vector<int>> &vec, int n, int m) {
    vector<vector<int>> loCol(n + 1, vector<int>(m + 1));
    vector<vector<int>> hiCol(n + 1, vector<int>(m + 1));
    vector<vector<int>> hiRow(n + 1, vector<int>(m + 1));

    for (int j = 1; j <= m; j++) {
        int curLo = INT_MAX, curHi = INT_MIN;
        for (int i = n; i >= 1; i--) {
            loCol[i][j] = curLo = min(curLo, vec[i][j]);
            hiCol[i][j] = curHi = max(curHi, vec[i][j]);
        }
    }

    for (int i = 1; i <= n; i++) {
        int curLo = INT_MAX, curHi = INT_MIN;
        //lo[i][0] = curLo, hi[i][0] = curHi;
        for (int j = 1; j <= m; j++) {
            lo[i][j] = curLo = min(curLo, loCol[i][j]);
            hi[i][j] = curHi = max(curHi, hiCol[i][j]);
        }
        curHi = INT_MIN;
        for (int j = m; j >= 1; j--)
            hiRow[i][j] = curHi = max(curHi, vec[i][j]);
    }

    priority_queue<tt> pqLo, pqHi;
    for (int i = 1; i <= n; i++) {
        bound[i] = m + 1;
        for (int j = 1; j <= m; j++) {
            pqLo.push(make_tuple(-lo[i][j], i, j));
            pqHi.push(make_tuple( hi[i][j], i, j));
            contain[getID(vec[i][j])].push_back({i, j});
        }
    }

    for (int k = 0; k < cmp.size(); k++) {
        for (auto [row, col] : contain[k])
            while (bound[row] > 1 && hiRow[row][bound[row] - 1] <= cmp[k]) bound[row]--;
        while (pqLo.size()) {
            int val, i, j; tie(val, i, j) = pqLo.top();
            if (ok(i, j)) break;
            else pqLo.pop();
        }
        while (pqHi.size()) {
            int val, i, j; tie(val, i, j) = pqHi.top();
            if (ok(i, j)) break;
            else pqHi.pop();
        }

        calcLo[k] = (pqLo.size() ? -get<0>(pqLo.top()) : INT_MAX);
        calcHi[k] = (pqHi.size() ?  get<0>(pqHi.top()) : INT_MIN);
    }

    int ans = 0;
    if (!check(0)) {
        for (int i = 29; i >= 0; i--) {
            int mask = ans | (1 << i);
            if (!check(mask)) ans |= (1 << i);
        }
        ans++;
    }

    for (int k = 0; k < cmp.size(); k++)
        contain[k].clear();
    return ans;
}

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

    int n, m; cin >> n >> m;
    vector<vector<int>> vec(n + 1, vector<int>(m + 1));
    vector<vector<int>> rot(m + 1, vector<int>(n + 1));

    //cmp.push_back(0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> vec[i][j];
            rot[j][n - i + 1] = vec[i][j];
            cmp.push_back(vec[i][j]);
        }
    }
    sort(all(cmp)); filter(cmp);

    cout << min(solve(vec, n, m), solve(rot, m, n));

    return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'bool check(int)':
joioi.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int k = 0; k < cmp.size(); k++) {
      |                     ~~^~~~~~~~~~~~
joioi.cpp:31:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         while (pos + 1 < cmp.size() && cmp[pos + 1] < cmp[k] - delta) {
      |                ~~~~~~~~^~~~~~~~~~~~
joioi.cpp:33:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |             for (auto [row, col] : contain[pos]) {
      |                       ^
joioi.cpp: In function 'int solve(std::vector<std::vector<int> >&, int, int)':
joioi.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for (int k = 0; k < cmp.size(); k++) {
      |                     ~~^~~~~~~~~~~~
joioi.cpp:81:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |         for (auto [row, col] : contain[k])
      |                   ^
joioi.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for (int k = 0; k < cmp.size(); k++)
      |                     ~~^~~~~~~~~~~~

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