제출 #601274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
601274		MohamedFaresNebili	Rectangles (IOI19_rect)	C++14	25 / 100	581 ms	54240 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

            using namespace std;

            using ll = long long;
            using ii = pair<ll, ll>;
            using vi = vector<int>;

            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound

            const int oo = 1000 * 1000 * 1000 + 7;

            int ST[40004];
            int R[100][100][100], C[100][100][100];
            void update(int v, int l, int r, int p, int val) {
                if(l == r) {
                    ST[v] = val;
                    return;
                }
                int md = (l + r) / 2;
                if(p <= md) update(v * 2, l, md, p, val);
                else update(v * 2 + 1, md + 1, r, p, val);
                ST[v] = max(ST[v * 2], ST[v * 2 + 1]);
            }
            int query(int v, int l, int r, int lo, int hi) {
                if(l > hi || r < lo) return 0;
                if(l >= lo && r <= hi) return ST[v];
                return max(query(v * 2, l, (l + r) / 2, lo, hi),
                           query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
            }

            ll count_rectangles(vector<vector<int>> A) {
                int N = A.size(), M = A[0].size();
              	ll res = 0;
              	if(N == 3) {
                    for(int l = 1; l < M - 1; l++) {
                        if(A[1][l] >= A[0][l] || A[1][l] >= A[2][l])
                            update(1, 0, M - 1, l, 1000000007);
                        else update(1, 0, M - 1, l, A[1][l]);
                    }
                    for(int l = 1; l < M - 1; l++) {
                        for(int i = l; i < M - 1; i++) {
                            int V = query(1, 0, M - 1, l, i);
                            res += (V < A[1][l - 1] && V < A[1][i + 1]);
                        }
                    }
              	}
              	if(N > 3) {
              	    for(int l = 1; l < N - 1; l++) {
                        for(int i = 1; i < M - 1; i++) {
                            R[l][i][i] = A[l][i];
                        }
                        for(int i = 1; i < M - 1; i++) {
                            for(int j = i + 1; j < M - 1; j++) {
                                R[l][i][j] = max(R[l][i][j - 1], A[l][j]);
                            }
                        }
              	    }
              	    for(int l = 1; l < M - 1; l++) {
                        for(int i = 1; i < N - 1; i++) {
                            C[l][i][i] = A[i][l];
                        }
                        for(int i = 1; i < N - 1; i++) {
                            for(int j = i + 1; j < N - 1; j++) {
                                C[l][i][j] = max(C[l][i][j - 1], A[j][l]);
                            }
                        }
              	    }
              	    for(int l = 1; l < N - 1; l++) {
                        for(int i = 1; i < M - 1; i++) {
                            for(int j = l; j < N - 1; j++) {
                                for(int k = i; k < M - 1; k++) {
                                    bool ok = 1;
                                    for(int x = l; x <= j; x++)
                                        ok &= (R[x][i][k] < A[x][i - 1] && R[x][i][k] < A[x][k + 1]);
                                    if(C[k][l][j] >= A[l - 1][k] || C[k][l][j] >= A[j + 1][k]) break;
                                    res += ok;
                                }
                            }
                        }
              	    }
              	}
                return res;
            }

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