Submission #766781

#	Time	Username	Problem	Language	Result	Execution time	Memory
766781		t6twotwo	Rectangles (IOI19_rect)	C++17	0 / 100	100 ms	245876 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];
struct sparse_table {
    int n, e;
    int (*f)(int, int);
    vector<vector<int>> st;
    sparse_table() {
    }
    sparse_table(vector<int> &a, int (*_f)(int, int), int _e) : n(a.size()), f(_f), e(_e) {
        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) {
        if (l == r) {
            return e;
        }
        int k = lg[r - l];
        return f(st[l][k], st[r - (1 << k)][k]);
    }
};
int fmin(int x, int y) {
    return min(x, y);
}
int fmax(int x, int y) {
    return max(x, y);
}
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();
    int k = 2500;
    vector A0(k, vector<int>(k));
    vector A1(k, vector<int>(k));
    vector A2(k, vector<int>(k));
    vector A3(k, vector<int>(k));
    vector A4(k, vector<int>(k));
    vector A5(k, vector<int>(k));
    vector A6(k, vector<int>(k));
    vector A7(k, vector<int>(k));
    vector A8(k, vector<int>(k));
    vector A9(k, vector<int>(k));
    // 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 L(n, vector<int>(m));
    // vector R(n, vector<int>(m));
    // vector D(n, vector<int>(m));
    // vector U(n, vector<int>(m));
    // for (int i = 0; i < n; i++) {
    //     L[i] = ms(a[i], 0);
    //     R[i] = ms(a[i], 1);
    // }
    // 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<sparse_table> SL(m), SR(m), SU(n), SD(n);
    // for (int i = 0; i < n; i++) {
    //     vector<int> u(m), d(m);
    //     for (int j = 0; j < m; j++) {
    //         u[j] = U[i][j];
    //         d[j] = D[i][j];
    //     }
    //     SU[i] = sparse_table(u, fmax, -1);
    //     SD[i] = sparse_table(d, fmin, n);
    // }
    // for (int i = 0; i < m; i++) {
    //     vector<int> l(n), r(n);
    //     for (int j = 0; j < n; j++) {
    //         l[j] = L[j][i];
    //         r[j] = R[j][i];
    //     }
    //     SL[i] = sparse_table(l, fmax, -1);
    //     SR[i] = sparse_table(r, fmin, m);
    // }
    // auto L = [&](int i, int j) {
    //     return SL[j].st[i][0];
    // };
    // auto R = [&](int i, int j) {
    //     return SR[j].st[i][0];
    // };
    // auto U = [&](int i, int j) {
    //     return SU[i].st[j][0];
    // };
    // auto D = [&](int i, int j) {
    //     return SD[i].st[j][0];
    // };
    // auto check = [&](int x1, int y1, int x2, int y2) -> int {
    //     if (x1 > x2 || y1 > y2 || x1 < 1 || y1 < 1 || x2 >= n - 1 || y2 >= m - 1) {
    //         return 0;
    //     }
    //     if (SD[x1 - 1].query(y1, y2 + 1) <= x2) {
    //         return 0;
    //     }
    //     if (SU[x2 + 1].query(y1, y2 + 1) >= x1) {
    //         return 0;
    //     }
    //     if (SR[y1 - 1].query(x1, x2 + 1) <= y2) {
    //         return 0;
    //     }
    //     if (SL[y2 + 1].query(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) {
    //                 ans += check(i, j, D[i - 1][j] - 1, R[i][j - 1] - 1);
    //             }
    //         }
    //     }
    //     return ans;
    // }
    // vector T(n, vector<vector<int>>(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;
}

Compilation message (stderr)

rect.cpp: In constructor 'sparse_table::sparse_table(std::vector<int>&, int (*)(int, int), int)':
rect.cpp:22:11: warning: 'sparse_table::f' will be initialized after [-Wreorder]
   22 |     int (*f)(int, int);
      |           ^
rect.cpp:21:12: warning:   'int sparse_table::e' [-Wreorder]
   21 |     int n, e;
      |            ^
rect.cpp:26:5: warning:   when initialized here [-Wreorder]
   26 |     sparse_table(vector<int> &a, int (*_f)(int, int), int _e) : n(a.size()), f(_f), e(_e) {
      |     ^~~~~~~~~~~~
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:55:9: warning: unused variable 'n' [-Wunused-variable]
   55 |     int n = a.size();
      |         ^
rect.cpp:56:9: warning: unused variable 'm' [-Wunused-variable]
   56 |     int m = a[0].size();
      |         ^
rect.cpp:193:1: warning: no return statement in function returning non-void [-Wreturn-type]
  193 | }
      | ^

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