Submission #364422

#	Time	Username	Problem	Language	Result	Execution time	Memory
364422		arujbansal	Rectangles (IOI19_rect)	C++17	37 / 100	5071 ms	28396 KiB

rect

#include <iostream>
#include <random>
#include <chrono>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <queue>

using namespace std;

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epock().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
// #define int long long

const int MXN = 1e5 + 1, INF = 1e9 + 5;

bool valid(int r1, int c1, int r2, int c2, vector<vector<int>> &a) {
    int N = sz(a), M = sz(a.back());

    for (int i = r1; i <= r2; i++) {
        for (int j = c1; j <= c2; j++) {
            if (a[i][j] >= a[r1 - 1][j] || a[i][j] >= a[r2 + 1][j]) return false;
            if (a[i][j] >= a[i][c1 - 1] || a[i][j] >= a[i][c2 + 1]) return false;
        }
    }

    return true;
}

int64_t count_rectangles(vector<vector<int>> a) {
    int64_t ans = 0;

    int N = sz(a), M = sz(a.back());

    for (int r1 = 1; r1 < N - 1; r1++) {
        for (int c1 = 1; c1 < M - 1; c1++) {
            for (int r2 = r1; r2 < N - 1; r2++) {
                for (int c2 = c1; c2 < M - 1; c2++) {
                    ans += valid(r1, c1, r2, c2, a);
                }
            }
        }
    }

    return ans;
}

// void solve() {
    
// }   

// signed main() {
//     ios_base::sync_with_stdio(false);
//     cin.tie(nullptr);

//     int TC = 1;
//     // cin >> TC;
//     while (TC--) solve();
// }

Compilation message (stderr)

rect.cpp: In function 'bool valid(int, int, int, int, std::vector<std::vector<int> >&)':
rect.cpp:26:9: warning: unused variable 'N' [-Wunused-variable]
   26 |     int N = sz(a), M = sz(a.back());
      |         ^
rect.cpp:26:20: warning: unused variable 'M' [-Wunused-variable]
   26 |     int N = sz(a), M = sz(a.back());
      |                    ^

• 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