Submission #766802

#	Time	Username	Problem	Language	Result	Execution time	Memory
766802		t6twotwo	Rectangles (IOI19_rect)	C++17	59 / 100	837 ms	1048576 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int lg[2501];
int SL[2500][2500][12];
int SR[2500][2500][12];
int SU[2500][2500][12];
int SD[2500][2500][12];
int SLQ(int y, int l, int r) {
    if (l == r) {
        return -1;
    }
    int k = lg[r - l];
    return max(SL[y][l][k], SL[y][r - (1 << k)][k]);
}
int SRQ(int y, int l, int r) {
    if (l == r) {
        return 2500;
    }
    int k = lg[r - l];
    return min(SR[y][l][k], SR[y][r - (1 << k)][k]);
}
int SUQ(int x, int l, int r) {
    if (l == r) {
        return -1;
    }
    int k = lg[r - l];
    return max(SU[x][l][k], SU[x][r - (1 << k)][k]);
};
int SDQ(int x, int l, int r) {
    if (l == r) {
        return 2500;
    }
    int k = lg[r - l];
    return min(SD[x][l][k], SD[x][r - (1 << k)][k]);
};
ll count_rectangles(vector<vector<int>> a) {
    for (int i = 2; i <= 2500; i++) {
        lg[i] = lg[i / 2] + 1;
    }
    int n = a.size();
    int m = a[0].size();
    bool subtask6 = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] > 1) {
                subtask6 = 0;
            }
        }
    }
    vector<int> stk;
    int L[n][m], R[n][m], U[n][m], D[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            while (!stk.empty() && a[i][stk.back()] < a[i][j]) {
                stk.pop_back();
            }
            L[i][j] = stk.empty() ? -1 : stk.back();
            stk.push_back(j);
        }
        stk.clear();
        for (int j = m - 1; j >= 0; j--) {
            while (!stk.empty() && a[i][stk.back()] < a[i][j]) {
                stk.pop_back();
            }
            R[i][j] = stk.empty() ? m : stk.back();
            stk.push_back(j);
        }
        stk.clear();
    }
    for (int j = 0; j < m; j++) {
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && a[stk.back()][j] < a[i][j]) {
                stk.pop_back();
            }
            U[i][j] = stk.empty() ? -1 : stk.back();
            stk.push_back(i);
        }
        stk.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stk.empty() && a[stk.back()][j] < a[i][j]) {
                stk.pop_back();
            }
            D[i][j] = stk.empty() ? n : stk.back();
            stk.push_back(i);
        }
        stk.clear();
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            SU[i][j][0] = U[i][j];
            SD[i][j][0] = D[i][j];
        }
        for (int j = 0; j < lg[m]; j++) {
            for (int k = 0; k + (2 << j) <= m; k++) {
                SU[i][k][j + 1] = max(SU[i][k][j], SU[i][k + (1 << j)][j]);
                SD[i][k][j + 1] = min(SD[i][k][j], SD[i][k + (1 << j)][j]);
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            SL[i][j][0] = L[j][i];
            SR[i][j][0] = R[j][i];
        }
        for (int j = 0; j < lg[n]; j++) {
            for (int k = 0; k + (2 << j) <= n; k++) {
                SL[i][k][j + 1] = max(SL[i][k][j], SL[i][k + (1 << j)][j]);
                SR[i][k][j + 1] = min(SR[i][k][j], SR[i][k + (1 << j)][j]);
            }
        }
    }
    auto check = [&](int x1, int y1, int x2, int y2) -> int {
        if (x1 > x2 || y1 > y2) {
            return 0;
        }
        if (SDQ(x1 - 1, y1, y2 + 1) <= x2) {
            return 0;
        }
        if (SUQ(x2 + 1, y1, y2 + 1) >= x1) {
            return 0;
        }
        if (SRQ(y1 - 1, x1, x2 + 1) <= y2) {
            return 0;
        }
        if (SLQ(y2 + 1, x1, x2 + 1) >= y1) {
            return 0;
        }
        return 1;
    };
    int ans = 0;
    if (subtask6) {
        for (int i = 1; i < n - 1; i++) {
            for (int j = 1; j < m - 1; j++) {
                if (a[i][j] == 0 && a[i - 1][j] == 1 && a[i][j - 1] == 1) {
                    if (D[i - 1][j] != n && R[i][j - 1] != m) {
                        ans += check(i, j, D[i - 1][j] - 1, R[i][j - 1] - 1);
                    }
                }
            }
        }
        return ans;
    }
    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 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) {
                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);
                    }
                }
            }
            y = L[i][j + 1] + 1;
            if (y != 0 && a[i][j + 1] != a[i][y - 1]) {
                int x = D[i - 1][j] - 1;
                if (x != n - 1) {
                    ans += check(i, y, x, j);
                }
                for (int k : T[i - 1][j]) {
                    if (a[i - 1][j] != a[k][j]) {
                        ans += check(i, y, k - 1, j);
                    }
                }
            }
        }
    }
    return ans;
}

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