제출 #412506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
412506		timmyfeng	Rectangles (IOI19_rect)	C++17	100 / 100	3376 ms	278492 KiB

rect

#include <bits/stdc++.h>
using namespace std;
 
const int N = 2500;

short l[N][N], r[N][N], u[N][N], d[N][N];
short lu[N][N], ru[N][N], ul[N][N], dl[N][N];
short mono[N];
 
array<short, 4> rects[8 * N * N];
 
long long count_rectangles(vector<vector<int>> a) {
    short n = a.size(), m = a[0].size();
 
    for (short i = 0; i < n; ++i) {
        for (short j = 0; j < m; ++j) {
            l[i][j] = r[i][j] = u[i][j] = d[i][j] = -1;
        }
    }
 
    for (short i = 0; i < n; ++i) {
        short top = -1;
        for (short j = 0; j < m; ++j) {
            while (top >= 0 && a[i][mono[top]] < a[i][j]) {
                short k = mono[top--];
                if (k + 1 <= j - 1) {
                    r[i][k + 1] = j - 1;
                }
            }

            if (top >= 0) {
                short k = mono[top];
                top -= a[i][k] == a[i][j];
                if (k + 1 <= j - 1) {
                    l[i][j - 1] = k + 1;
                }
            }
 
            mono[++top] = j;
        }
    }
 
    for (short i = 0; i < m; ++i) {
        short top = -1;
        for (short j = 0; j < n; ++j) {
            while (top >= 0 && a[mono[top]][i] < a[j][i]) {
                short k = mono[top--];
                if (k + 1 <= j - 1) {
                    d[k + 1][i] = j - 1;
                }
            }

            if (top >= 0) {
                short k = mono[top];
                top -= a[k][i] == a[j][i];
                if (k + 1 <= j - 1) {
                    u[j - 1][i] = k + 1;
                }
            }
 
            mono[++top] = j;
        }
    }

    for (short i = 0; i < n; ++i) {
        for (short j = 0; j < m; ++j) {
            if (l[i][j] != -1) {
                if (i > 0 && l[i][j] == l[i - 1][j]) {
                    lu[i][j] = lu[i - 1][j];
                } else if (i > 0 && r[i - 1][l[i][j]] == j) {
                    lu[i][j] = ru[i - 1][l[i][j]];
                } else {
                    lu[i][j] = i;
                }
            }

            if (r[i][j] != -1) {
                if (i > 0 && r[i][j] == r[i - 1][j]) {
                    ru[i][j] = ru[i - 1][j];
                } else if (i > 0 && l[i - 1][r[i][j]] == j) {
                    ru[i][j] = lu[i - 1][r[i][j]];
                } else {
                    ru[i][j] = i;
                }
            }
        }
    }
 
    for (short j = 0; j < m; ++j) {
        for (short i = 0; i < n; ++i) {
            if (u[i][j] != -1) {
                if (j > 0 && u[i][j] == u[i][j - 1]) {
                    ul[i][j] = ul[i][j - 1];
                } else if (j > 0 && d[u[i][j]][j - 1] == i) {
                    ul[i][j] = dl[u[i][j]][j - 1];
                } else {
                    ul[i][j] = j;
                }
            }

            if (d[i][j] != -1) {
                if (j > 0 && d[i][j] == d[i][j - 1]) {
                    dl[i][j] = dl[i][j - 1];
                } else if (j > 0 && u[d[i][j]][j - 1] == i) {
                    dl[i][j] = ul[d[i][j]][j - 1];
                } else {
                    dl[i][j] = j;
                }
            }
        }
    }

    int ans = 0;
    for (short i1 = 0; i1 < n; ++i1) {
        for (short j1 = 0; j1 < m; ++j1) {
            for (auto i2 : {u[i1][j1], d[i1][j1]}) {
                if (i2 == -1) {
                    continue;
                }

                for (auto i : {i1, i2}) {
                    for (auto j2 : {l[i][j1], r[i][j1]}) {
                        if (j2 == -1) {
                            continue;
                        }

                        short iu = min(i1, i2), id = max(i1, i2);
                        short jl = min(j1, j2), jr = max(j1, j2);

                        if (!(l[id][jr] == jl && lu[id][jr] <= iu) && !(r[id][jl] == jr && ru[id][jl] <= iu)) {
                            continue;
                        }

                        if (!(u[id][jr] == iu && ul[id][jr] <= jl) && !(d[iu][jr] == id && dl[iu][jr] <= jl)) {
                            continue;
                        }

                        rects[ans++] = {iu, id, jl, jr};
                    }
                }
            }
        }
    }
 
    sort(rects, rects + ans);
 
    return unique(rects, rects + ans) - rects;
}

• 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