Submission #610784

#	Time	Username	Problem	Language	Result	Execution time	Memory
610784		lorenzoferrari	Rectangles (IOI19_rect)	C++17	13 / 100	4577 ms	277876 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
 
#define UP 0
#define LEFT 1
#define DOWN 2
#define RIGHT 3
 
int n, m;

/**/
constexpr int INF = 1e9;

const vector<array<int, 2>> dd{{0,1},{0,-1},{1,0},{-1,0}};

struct comp {
    int sz;
    array<int, 4> ext;
    comp() : sz(0), ext({INF, INF, -INF, -INF}) {}
    comp(int i, int j) : sz(1), ext({i,j,i,j}) {}
    bool good() {
        if (ext[UP] == 0 || ext[DOWN] == n-1) return false;
        if (ext[LEFT] == 0 || ext[RIGHT] == m-1) return false;
        return sz == (ext[DOWN] - ext[UP] + 1) * (ext[RIGHT] - ext[LEFT] + 1);
    }
};
comp join(const comp& a, const comp& b) {
    comp ans;
    ans.sz = a.sz + b.sz;
    ans.ext[UP] = min(a.ext[UP], b.ext[UP]);
    ans.ext[LEFT] = min(a.ext[LEFT], b.ext[LEFT]);
    ans.ext[DOWN] = max(a.ext[DOWN], b.ext[DOWN]);
    ans.ext[RIGHT] = max(a.ext[RIGHT], b.ext[RIGHT]);
    return ans;
}
/**/
void print(comp a) {
    cerr << "sz: " << a.sz << " ; ";
    cerr << "ext: ";
    for (int i = 0; i < 4; ++i) cerr << a.ext[i] << " ";
    cerr << "\n";
}

vector<int> p;
vector<comp> cc;

int findset(int v) {
    return (v == -1 || p[v] == v) ? v : p[v] = findset(p[v]);
}
bool unionset(int a, int b) {
    a = findset(a);
    b = findset(b);
    if (a == b || a == -1 || b == -1) return false;
    if (cc[a].sz < cc[b].sz) swap(a, b);
    p[b] = a;
    // cerr << "union (" << a/m << "," << a%m << "), (" << b/m << "," << b%m << ")\n";
    cc[a] = join(cc[a], cc[b]);
    return true;
}

LL count_rectangles(vector<vector<int>> a) {
    n = a.size();
    m = a[0].size();

    p.assign(n*m, -1);
    cc.resize(n*m);

    int mx = 0;
    for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {
        mx = max(mx, a[i][j]);
    }

    vector<vector<array<int, 2>>> v(mx + 1);
    for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {
        v[a[i][j]].push_back({i, j});
    }

    vector<int> last_time(n*m, -1);
    auto add_tile = [&](int i, int j) -> void {
        int id = m*i + j;
        p[id] = id;
        cc[id] = comp(i, j);
        for (auto [dx, dy] : dd) {
            int nx = i + dx;
            int ny = j + dy;
            if (0 > nx || nx >= n || 0 > ny || ny >= m) continue;
            unionset(m*i+j, m*nx+ny);
        }
    };

    LL ans = 0;
    for (int i = 0; i <= mx; ++i) {
        for (auto [x, y] : v[i]) {
            add_tile(x, y);
        }
        for (auto [x, y] : v[i]) {
            int id = findset(m*x + y);
            if (last_time[id] != i) {
                last_time[id] = i;
                ans += cc[id].good();
                if (cc[id].good()) {
                    print(cc[id]);
                }
            }
        }
    }
    return ans;

#if 0
    if (mx <= 1) {
        /**/
        vector<vector<bool>> vis(n, vector<bool>(m, false));
        for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {
            if (vis[i][j] || a[i][j] == 1) continue;
            comp cur(i, j);
            queue<array<int, 2>> Q;
            Q.push({i, j});
            vis[i][j] = true;
            while (!Q.empty()) {
                auto [x, y] = Q.front();
                Q.pop();
                for (auto [dx, dy] : dd) {
                    int nx = x + dx;
                    int ny = y + dy;
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                    if (vis[nx][ny] || a[nx][ny] == 1) continue;
                    vis[nx][ny] = true;
                    Q.push({nx, ny});
                    cur = join(cur, comp(nx, ny));
                }
            }
            ans += cur.good();
        }
        
        return ans;
        /**/
    }

    vector<vector<array<int, 4>>> ext(n, vector<array<int, 4>>(m));
    
    // LEFT & RIGHT
    for (int i = 0; i < n; ++i) {
        auto v = a[i];
        auto nxt = next_geq_val(v);
        auto prv = prev_geq_val(v);
        for (int j = 0; j < m; ++j) {
            ext[i][j][LEFT] = prv[j];
            ext[i][j][RIGHT] = nxt[j];
        }
    }
    // UP & DOWN
    for (int j = 0; j < m; ++j) {
        vector<int> v(n);
        for (int i = 0; i < n; ++i) v[i] = a[i][j];
        auto nxt = next_geq_val(v);
        auto prv = prev_geq_val(v);
        for (int i = 0; i < n; ++i) {
            ext[i][j][UP] = prv[i];
            ext[i][j][DOWN] = nxt[i];
        }
    }
 
    LL ans = 0;
    for (int r = 0; r < n; ++r) for (int c = 0; c < m; ++c) {
        int rwall = m-1;
        for (int rr = r+2; rr < n; ++rr) {
            rwall = min(rwall, ext[rr-1][c][RIGHT]);
            int dwall = n-1;
            for (int cc = c+2; cc <= rwall; ++cc) {
                dwall = min(dwall, ext[r][cc-1][DOWN]);
                if (rr > dwall) break;
                bool works = true;
                // orizzontali
                for (int j = c+1; works && j < cc; ++j) {
                    // works &= (ext[r][j][DOWN] >= rr);
                    works &= (ext[rr][j][UP] <= r);
                }
                // verticali
                for (int i = r+1; works && i < rr; ++i) {
                    // works &= (ext[i][c][RIGHT] >= cc);
                    works &= (ext[i][cc][LEFT] <= c);
                }
                ans += works;
            }
        }
    }
 
    return ans;
#endif
}

• 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