Submission #766975

#	Time	Username	Problem	Language	Result	Execution time	Memory
766975		t6twotwo	Rectangles (IOI19_rect)	C++17	100 / 100	4613 ms	733456 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> ms(vector<int> &a, bool f) {
    int n = a.size();
    vector<int> b(n, f ? n : -1), stk;
    for (int i = (f ? n - 1 : 0); i != (f ? -1 : n); i += (f ? -1 : 1)) {
        while (!stk.empty() && a[stk.back()] < a[i]) {
            stk.pop_back();
        }
        if (!stk.empty()) {
            b[i] = stk.back();
        }
        stk.push_back(i);
    }
    return b;
}
int lg[2501];
template <class S>
struct sparse_table {
    int n;
    S e;
    S (*f)(S, S);
    S st[2500][12];
    sparse_table() {
    }
    sparse_table(vector<S> &a, S (*_f)(S, S), S _e) : n(a.size()), f(_f), e(_e) {
        for (int i = 0; i < n; i++) {
            st[i][0] = a[i];
        }
        for (int j = 0; j < lg[n]; j++) {
            for (int i = 0; i + (2 << j) <= n; i++) {
                st[i][j + 1] = f(st[i][j], st[i + (1 << j)][j]);
            }
        }
    }
    S query(int l, int r) const {
        if (l == r) {
            return e;
        }
        int k = lg[r - l];
        return f(st[l][k], st[r - (1 << k)][k]);
    }
};
pair<int, int> F(pair<int, int> x, pair<int, int> y) {
    return {max(x.first, y.first), min(x.second, y.second)};
}
int fmin(int x, int y) {
    return min(x, y);
}
int fmax(int x, int y) {
    return max(x, y);
}
int n, m;
vector<vector<int>> a;
int L[2500][2500];
int R[2500][2500];
int U[2500][2500];
int D[2500][2500];
int DL[2500][2500];
int DR[2500][2500];
int UL[2500][2500];
int UR[2500][2500];
int LD[2500][2500];
int LU[2500][2500];
int RD[2500][2500];
int RU[2500][2500];
int ans = 0;
int check(int x1, int y1, int x2, int y2) {
    if (x1 > x2 || y1 > y2 || x1 < 1 || y1 < 1 || x2 >= n - 1 || y2 >= m - 1) {
        return 0;
    }
    assert(R[x1][y1 - 1] == y2 + 1);
    if (a[x1][y1 - 1] <= a[x1][y2 + 1]) {
        if (R[x1][y1 - 1] != y2 + 1) {
            return 0;
        }
        if (RD[x1][y1 - 1] <= x2) {
            return 0;
        }
    }
    if (a[x2][y1 - 1] <= a[x2][y2 + 1]) {
        if (R[x2][y1 - 1] != y2 + 1) {
            return 0;
        }
        if (RU[x2][y1 - 1] >= x1) {
            return 0;
        }
    }
    if (a[x2][y1 - 1] >= a[x2][y2 + 1]) {
        if (L[x2][y2 + 1] != y1 - 1) {
            return 0;
        }
        if (LU[x2][y2 + 1] >= x1) {
            return 0;
        }
    }
    if (a[x1 - 1][y1] <= a[x2 + 1][y1]) {
        if (D[x1 - 1][y1] != x2 + 1) {
            return 0;
        }
        if (DR[x1 - 1][y1] <= y2) {
            return 0;
        }
    }
    if (a[x1 - 1][y1] >= a[x2 + 1][y1]) {
        if (U[x2 + 1][y1] != x1 - 1) {
            return 0;
        }
        if (UR[x2 + 1][y1] <= y2) {
            return 0;
        }
    }
    if (a[x1 - 1][y2] <= a[x2 + 1][y2]) {
        if (D[x1 - 1][y2] != x2 + 1) {
            return 0;
        }
        if (DL[x1 - 1][y2] >= y1) {
            return 0;
        }
    }
    if (a[x1 - 1][y2] >= a[x2 + 1][y2]) {
        if (U[x2 + 1][y2] != x1 - 1) {
            return 0;
        }
        if (UL[x2 + 1][y2] >= y1) {
            return 0;
        }
    }
    return 1;
}
void solve(int eq) {
    for (int i = 0; i < n; i++) {
        auto l = ms(a[i], 0);
        auto r = ms(a[i], 1);
        copy(l.begin(), l.end(), L[i]);
        copy(r.begin(), r.end(), R[i]);
    }
    for (int j = 0; j < m; j++) {
        vector<int> v(n);
        for (int i = 0; i < n; i++) {
            v[i] = a[i][j];
        }
        auto u = ms(v, 0);
        auto d = ms(v, 1);
        for (int i = 0; i < n; i++) {
            U[i][j] = u[i];
            D[i][j] = d[i];
        }
    }
    vector<int> T[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (U[i][j] != -1) {
                T[U[i][j]][j].push_back(i);
            }
        }
    }
    for (int j = 1; j < m - 1; j++) {
        vector<pair<int, int>> v(n);
        for (int i = 0; i < n; i++) {
            v[i] = {L[i][j + 1], R[i][j - 1]};
        }
        sparse_table<pair<int, int>> s(v, F, {-1, m});
        for (int i = 0; i < n; i++) {
            if (i + 1 < n - 1 && D[i][j] != n) {
                tie(DL[i][j], DR[i][j]) = s.query(i + 1, D[i][j]);
            }
            if (i - 1 > 0 && U[i][j] != -1) {
                tie(UL[i][j], UR[i][j]) = s.query(U[i][j] + 1, i);
            }
        }
    }
    for (int i = 1; i < n - 1; i++) {
        vector<pair<int, int>> v(m);
        for (int j = 0; j < m; j++) {
            v[j] = {U[i + 1][j], D[i - 1][j]};
        }
        sparse_table<pair<int, int>> s(v, F, {-1, n});
        for (int j = 0; j < m; j++) {
            if (j + 1 < m - 1 && R[i][j] != m) {
                tie(RU[i][j], RD[i][j]) = s.query(j + 1, R[i][j]);
            }
            if (j - 1 > 0 && L[i][j] != -1) {
                tie(LU[i][j], LD[i][j]) = s.query(L[i][j] + 1, j);
            }
        }
    }
    for (int i = 1; i < n - 1; i++) {
        for (int j = 1; j < m - 1; j++) {
            int y = R[i][j - 1] - 1;
            if (y != m - 1 && (eq || a[i][j - 1] != a[i][y + 1])) {
                int x = D[i - 1][j] - 1;
                if (x != n - 1) {
                    ans += check(i, j, x, y);
                }
                for (int k : T[i - 1][j]) {
                    if (a[i - 1][j] != a[k][j]) {
                        ans += check(i, j, k - 1, y);
                    }
                }
            }
        }
    }
}
ll count_rectangles(vector<vector<int>> A) {
    swap(a, A);
    for (int i = 2; i <= 2500; i++) {
        lg[i] = lg[i / 2] + 1;
    }
    n = a.size();
    m = a[0].size();
    solve(1);
    for (int i = 0; i < n; i++) {
        reverse(a[i].begin(), a[i].end());
    }
    solve(0);
    return ans;
}

Compilation message (stderr)

rect.cpp: In instantiation of 'sparse_table<S>::sparse_table(std::vector<_Tp>&, S (*)(S, S), S) [with S = std::pair<int, int>]':
rect.cpp:165:53:   required from here
rect.cpp:24:9: warning: 'sparse_table<std::pair<int, int> >::f' will be initialized after [-Wreorder]
   24 |     S (*f)(S, S);
      |         ^
rect.cpp:23:7: warning:   'std::pair<int, int> sparse_table<std::pair<int, int> >::e' [-Wreorder]
   23 |     S e;
      |       ^
rect.cpp:28:5: warning:   when initialized here [-Wreorder]
   28 |     sparse_table(vector<S> &a, S (*_f)(S, S), S _e) : n(a.size()), f(_f), e(_e) {
      |     ^~~~~~~~~~~~

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