Submission #725374

#	Time	Username	Problem	Language	Result	Execution time	Memory
725374		t6twotwo	Rectangles (IOI19_rect)	C++17	37 / 100	5015 ms	1048576 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> F(vector<int> A) {
    int N = A.size();
    vector<int> B(N, -1), stk;
    for (int i = 0; i < N; i++) {
        while (!stk.empty() && (A[stk.back()] < A[i])) {
            stk.pop_back();
        }
        if (!stk.empty()) {
            B[i] = stk.back();
        }
        stk.push_back(i);
    }
    return B;
}
vector<int> G(vector<int> A) {
    int N = A.size();
    vector<int> B(N);
    for (int i = 0; i < N; i++) {
        B[N - 1 - i] = N - 1 - A[i];
    }
    return B;
}
const int emax = -1;
int fmax(int x, int y) {
    return max(x, y);
}
const int emin = 3000;
int fmin(int x, int y) {
    return min(x, y);
}
const int N = 2500;
int lg[N + 1];
void init() {
    lg[1] = 0;
    for (int i = 2; i <= N; i++) {
        lg[i] = lg[i / 2] + 1;
    }
}
template <int (*f)(int, int), int e>
struct sparse_table {
    int n;
    vector<vector<int>> st;
    sparse_table() {
    }
    sparse_table(vector<int> a) : n(a.size()) {
        st = vector(n, vector<int>(lg[n] + 1, 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]);
            }
        }
    }
    int query(int l, int r) {
        assert(l <= r);
        if (l == r) {
            return e;
        }
        int k = lg[r - l];
        return f(st[l][k], st[r - (1 << k)][k]);
    }
};
using smin = sparse_table<fmin, emin>;
using smax = sparse_table<fmax, emax>;
long long count_rectangles(vector<vector<int>> A) {
    init();
    int N = A.size();
    int M = A[0].size();
    vector 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];
        }
    }
    vector<vector<int>> L(N), R(N);
    for (int i = 0; i < N; i++) {
        L[i] = F(A[i]);
        R[i] = G(F(vector(A[i].rbegin(), A[i].rend())));
    }
    vector<vector<int>> U(M), D(M);
    for (int j = 0; j < M; j++) {
        U[j] = F(B[j]);
        D[j] = G(F(vector(B[j].rbegin(), B[j].rend())));
    }
    vector<smax> SL(M);
    vector<smin> SR(M);
    for (int j = 0; j < M; j++) {
        vector<int> AL(N), AR(N);
        for (int i = 0; i < N; i++) {
            AL[i] = L[i][j];
            AR[i] = R[i][j];
        }
        SL[j] = smax(AL);
        SR[j] = smin(AR);
    }
    vector<smax> SU(N);
    vector<smin> SD(N);
    for (int i = 0; i < N; i++) {
        vector<int> AU(M), AD(M);
        for (int j = 0; j < M; j++) {
            AU[j] = U[j][i];
            AD[j] = D[j][i];
        }
        SU[i] = smax(AU);
        SD[i] = smin(AD);
    }
    int ans = 0;
    auto check = [&](int x1, int x2, int y1, int y2) {
        if (SR[y1 - 1].query(x1, x2) < y2) return;
        if (SD[x1 - 1].query(y1, y2) < x2) return;
        if (SL[y2].query(x1, x2) >= y1) return;
        if (SU[x2].query(y1, y2) >= x1) return;
        ans++;
    };
    for (int i = 1; i < N - 1; i++) {
        for (int j = 1; j < M - 1; j++) {
            int u = R[i][j - 1];
            int v = L[i][j + 1];
            for (int k = i + 1; k < N; k++) {
                if (j < u && u < M) {
                    check(i, k, j, u);
                }
                if (0 <= v && v < j && A[i][j + 1] != A[i][v]) {
                    check(i, k, v + 1, j + 1);
                }
            }
        }
    }
    return ans;
}

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