Submission #815817

#	Time	Username	Problem	Language	Result	Execution time	Memory
815817		resting	Rectangles (IOI19_rect)	C++17	0 / 100	101 ms	165216 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

int n, m;

int id(int x, int y) { return x + y * n; }

struct val {
    int cnt, x1, y1, x2, y2;
    bool used = 0;
    val(int x, int y) : cnt(1), x1(x), x2(x), y1(y), y2(y) {};
    val() :val(-1, -1) {};
};
val ad(val a, val b) {
    a.x1 = min(a.x1, b.x1);
    a.x2 = max(a.x2, b.x2);
    a.y1 = min(a.y1, b.y1);
    a.y2 = max(a.y2, b.y2);
    a.cnt += b.cnt;
    a.used = 0;
    return a;
}
bool is(val a) {
    return (a.x2 - a.x1 + 1) * (a.y2 - a.y1 + 1) == a.cnt && !a.used;
}

struct dsu {
    vector<int> p;
    vector<val> d;
    dsu() {
        p = vector<int>(n * m, -1);
        d = vector<val>(n * m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                d[id(i, j)] = val(i, j);
            }
        }
    }
    int getp(int v) {
        return p[v] == -1 ? v : p[v] = getp(p[v]);
    }
    void merge(int a, int b) {
        a = getp(a); b = getp(b);
        if (a == b) return;
        if (d[a].cnt < d[b].cnt) swap(a, b);
        d[a] = ad(d[a], d[b]);
        p[b] = a;
    }
};

bool in_bounds(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}

int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };

const int mx = 7e6 + 5;
long long count_rectangles(std::vector<std::vector<int>> a) {
    n = a.size(); m = a[0].size();
    dsu ac;
    vector<pair<int, int>> uwu[mx];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            uwu[a[i][j]].push_back({ i, j });
        }
    }
    vector<vector<int>> active(n, vector<int>(m, 0));
    int res = 0;
    for (int i = 0; i < mx; i++) {
        for (auto& t : uwu[i]) {
            auto [x, y] = t;
            active[x][y] = 1;
            for (int j = 0; j < 4; j++) {
                int x2 = x + dx[j], y2 = y + dy[j];
                if (!in_bounds(x2, y2) || !active[x2][y2]) continue;
                ac.merge(id(x, y), id(x2, y2));
            }
        }
        for (auto& t : uwu[i]) {
            auto [x, y] = t;
            int v = ac.getp(id(x, y));
            if (is(ac.d[v])) {
                ac.d[v].used = 1; res++;
            }
        }
    }
    return res;
}

Compilation message (stderr)

rect.cpp: In constructor 'val::val(int, int)':
rect.cpp:10:22: warning: 'val::x2' will be initialized after [-Wreorder]
   10 |     int cnt, x1, y1, x2, y2;
      |                      ^~
rect.cpp:10:18: warning:   'int val::y1' [-Wreorder]
   10 |     int cnt, x1, y1, x2, y2;
      |                  ^~
rect.cpp:12:5: warning:   when initialized here [-Wreorder]
   12 |     val(int x, int y) : cnt(1), x1(x), x2(x), y1(y), y2(y) {};
      |     ^~~

• 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