Submission #264595

#	Time	Username	Problem	Language	Result	Execution time	Memory
264595		hamerin	Rectangles (IOI19_rect)	C++17	10 / 100	5055 ms	147960 KiB

rect

#include "rect.h"

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

vector<pi> findLegalTuple(const vector<int> &v) {
    vector<pi> ret;
    vector<size_t> seq;  // monotonic
    size_t sn = 0;

    for (size_t i = 0; i < v.size(); i++) {
        while (sn >= 1 && v[seq.back()] == v[i]) seq.pop_back(), --sn;
        seq.emplace_back(i), ++sn;

        // rearrangement
        while (sn >= 2 && v[seq[sn - 2]] < v[seq[sn - 1]]) {
            auto tmp = seq[sn - 1];
            seq.pop_back(), --sn;
            seq[sn - 1] = tmp;

            if (sn >= 2) ret.emplace_back(seq[sn - 2], seq[sn - 1]);
        }
    }

    return ret;
}

vector<pi> getMaxPos(const vector<int> &v) {
    size_t N = v.size();
    vector<pi> ret(N, {-1, -1});

    for (int i = N - 1; i >= 0; i--) {
        for (int j = i + 1; j < N; j++) {
            if (ret[j].first == -1 && v[i] > v[j]) ret[j].first = i;
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < i; j++) {
            if (ret[j].second == -1 && v[i] > v[j]) ret[j].second = i;
        }
    }

    return ret;
}

vector<pi> processToIntervals(const vector<pi> &v) {
    vector<pi> ret;

    for (auto [el, _] : v) {
        if (!ret.empty() && ret.back().second == el - 1)
            ret.back().second++;
        else
            ret.emplace_back(el, el);
    }

    return ret;
}

bool intervalBinarySearch(const vector<pi> &v, pi t) {
    if (v.empty()) return false;

    const size_t N = v.size();

    size_t r1 = -1;
    {
        size_t s = 0, e = N - 1;

        while (e - s >= 2) {
            size_t m = (s + e) >> 1;
            if (v[m].first <= t.first && t.first <= v[m].second) {
                r1 = m;
                break;
            }

            if (v[m].second < t.first) s = m + 1;
            if (v[m].first > t.first) e = m - 1;
        }

        if (v[s].first <= t.first && t.first <= v[s].second) r1 = s;
        if (v[e].first <= t.first && t.first <= v[e].second) r1 = e;
    }

    size_t r2 = -1;
    {
        size_t s = 0, e = N - 1;

        while (e - s >= 2) {
            size_t m = (s + e) >> 1;
            if (v[m].first <= t.second && t.second <= v[m].second) {
                r2 = m;
                break;
            }

            if (v[m].second < t.second) s = m + 1;
            if (v[m].first > t.second) e = m - 1;
        }

        if (v[s].first <= t.second && t.second <= v[s].second) r2 = s;
        if (v[e].first <= t.second && t.second <= v[e].second) r2 = e;
    }

    return r1 != -1 && r2 != -1 && r1 == r2;
}

i64 count_rectangles(vector<vector<int>> a) {
    const size_t N = a.size();
    const size_t M = a[0].size();

    // transpose
    vector<vector<int>> b(M, vector<int>(N));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) b[j][i] = a[i][j];

    // get Max Position
    vector<vector<pi>> aM(N, vector<pi>(M));
    vector<vector<pi>> bM(M, vector<pi>(N));

    for (int i = 0; i < N; i++) aM[i] = getMaxPos(a[i]);
    for (int i = 0; i < M; i++) bM[i] = getMaxPos(b[i]);

    // find Legal Tuple && assign
    vector<vector<vector<pi>>> aL(M, decltype(aL)::value_type(M));
    vector<vector<vector<pi>>> bL(N, decltype(bL)::value_type(N));

    for (int i = 0; i < N; i++) {
        auto Lg = findLegalTuple(a[i]);
        for (auto [l, r] : Lg) aL[l][r].emplace_back(i, 0);
    }
    for (int i = 0; i < M; i++) {
        auto Lg = findLegalTuple(b[i]);
        for (auto [l, r] : Lg) bL[l][r].emplace_back(i, 0);
    }

    for (auto &vec : aL)
        for (auto &el : vec) el = processToIntervals(el);
    for (auto &vec : bL)
        for (auto &el : vec) el = processToIntervals(el);

    // Main Logic
    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            auto [L, R] = aM[i][j];
            auto [T, B] = bM[j][i];
            if (L == -1 || R == -1 || T == -1 || B == -1) continue;

            if (intervalBinarySearch(aL[L][R], {T + 1, B - 1}) &&
                intervalBinarySearch(bL[T][B], {L + 1, R - 1}))
                ++ans;
        }
    }

    return ans;
}

Compilation message (stderr)

rect.cpp: In function 'std::vector<std::pair<int, int> > getMaxPos(const std::vector<int>&)':
rect.cpp:47:31: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (int j = i + 1; j < N; j++) {
      |                             ~~^~~
rect.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i = 0; i < N; i++) {
      |                     ~~^~~
rect.cpp: In function 'bool intervalBinarySearch(const std::vector<std::pair<int, int> >&, pi)':
rect.cpp:117:15: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  117 |     return r1 != -1 && r2 != -1 && r1 == r2;
      |            ~~~^~~~~
rect.cpp:117:27: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  117 |     return r1 != -1 && r2 != -1 && r1 == r2;
      |                        ~~~^~~~~
rect.cpp: In function 'i64 count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:126:23: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
  126 |     for (int i = 0; i < N; i++)
      |                     ~~^~~
rect.cpp:127:27: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
  127 |         for (int j = 0; j < M; j++) b[j][i] = a[i][j];
      |                         ~~^~~
rect.cpp:133:23: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
  133 |     for (int i = 0; i < N; i++) aM[i] = getMaxPos(a[i]);
      |                     ~~^~~
rect.cpp:134:23: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
  134 |     for (int i = 0; i < M; i++) bM[i] = getMaxPos(b[i]);
      |                     ~~^~~
rect.cpp:140:23: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
  140 |     for (int i = 0; i < N; i++) {
      |                     ~~^~~
rect.cpp:144:23: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
  144 |     for (int i = 0; i < M; i++) {
      |                     ~~^~~
rect.cpp:156:23: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
  156 |     for (int i = 0; i < N; i++) {
      |                     ~~^~~
rect.cpp:157:27: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
  157 |         for (int j = 0; j < M; j++) {
      |                         ~~^~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 10 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28