Submission #417686

#	Time	Username	Problem	Language	Result	Execution time	Memory
417686		usachevd0	Rectangles (IOI19_rect)	C++17	13 / 100	410 ms	136000 KiB

rect

#pragma gcc optimize("Ofast")
#pragma gcc optimize("O3")
#pragma gcc target("avx,avx2,fma,sse,sse2,sse3,popcnt")
#include <bits/stdc++.h>
#ifndef LOCAL
    #include "rect.h"
#endif

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
    return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
    return y > x ? (x = y, true) : false;
}
void debug_out() {
    cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
    cerr << ' ' << A;
    debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
    for (int i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}
#ifdef LOCAL
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
    for (auto& x : v)
        stream << x << ' ';
    return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << ' ' << p.second;
}

const int INF32 = 1e9;
const int maxN = 2503;
int a[maxN][maxN];
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
bool used[maxN][maxN];

pii qu[maxN * maxN];
int qt;

ll count_rectangles(vector<vector<int>> _a) {
    int n = _a.size(), m = _a[0].size();
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            a[i][j] = _a[i][j];
    if (min(n, m) < 3) return 0;
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (a[i][j] == 1 || used[i][j]) continue;
            
            qu[0] = {i, j};
            used[i][j] = 1;
            qt = 1;
            int cnt = 0;
            int minX = +INF32;
            int maxX = -INF32;
            int minY = +INF32;
            int maxY = -INF32;
            for (int qi = 0; qi < qt; ++qi) {
                int x = qu[qi].fi, y = qu[qi].se;
                ++cnt;
                chkmin(minX, x);
                chkmax(maxX, x);
                chkmin(minY, y);
                chkmax(maxY, y);
                for (int d = 0; d < 4; ++d) {
                    int x1 = x + dx[d];
                    int y1 = y + dy[d];
                    if (0 <= x1 && x1 < n && 0 <= y1 && y1 < m && !a[x1][y1] && !used[x1][y1]) {
                        used[x1][y1] = 1;
                        qu[qt++] = {x1, y1};
                    }
                }
            }
            if (1 <= minX && maxX <= n - 2 && 1 <= minY && maxY <= m - 2 && (maxX - minX + 1) * (maxY - minY + 1) == cnt)
                ++ans;
        }
    }
    return ans;
    return ans;
}


#ifdef LOCAL


int main() {
#ifdef LOCAL
    freopen("in", "r", stdin);
#endif
    // InputReader inputReader(STDIN_FILENO);
    int n, m;
    cin >> n >> m;
    // n = inputReader.readInt();
    // m = inputReader.readInt();
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            // a[i][j] = inputReader.readInt();
        }
    }
    // inputReader.close();
    
    auto oldTime = Time;
    long long result = count_rectangles(a);
    debug(Time - oldTime);

    printf("%lld\n", result);
    fclose(stdout);
    return 0;
}
#endif

Compilation message (stderr)

rect.cpp:1: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    1 | #pragma gcc optimize("Ofast")
      | 
rect.cpp:2: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    2 | #pragma gcc optimize("O3")
      | 
rect.cpp:3: warning: ignoring '#pragma gcc target' [-Wunknown-pragmas]
    3 | #pragma gcc target("avx,avx2,fma,sse,sse2,sse3,popcnt")
      |

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