Submission #1215057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215057		jasonic	Rectangles (IOI19_rect)	C++20	13 / 100	2970 ms	437280 KiB

rect

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

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)

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

struct DSU{
    vector<int> par, sz, minX, maxX, minY, maxY;
    vector<bool> invalid, active;
    
    DSU() {
        par = sz = minX = maxX = minY = maxY = vector<int>(n, 0);
        invalid = active = vector<bool>(n, false);
        for(int i = 0; i < n; i++) {
            par[i] = i;
            sz[i] = 1;
            minX[i] = maxX[i] = (c==0?0:i/c);
            minY[i] = maxY[i] = (c==0?i:i%c);
            invalid[i] = (i/c == 0 || i/c == r-1 || i%c == 0 || i%c == c-1);
            active[i] = false;
        }
    }

    int parent(int n) {
        if(par[n] != n) par[n] = parent(par[n]);
        return par[n];
    }

    void merge(int x1, int y1, int x2, int y2) {
        int a = parent(y1 + x1*c);
        int b = parent(y2 + x2*c);

        if(!(active[a] and active[b])) return;
        if(a == b) return;

        // cout << "merged " << x1 << ' ' << y1 << " to " << x2 << ' ' << y2 << '\n';

        if(!(sz[a] > sz[b])) swap(a, b);
        sz[a] += sz[b];
        par[b] = a;
        invalid[a] = invalid[a] | invalid[b];
        minX[a] = min(minX[a], minX[b]);
        maxX[a] = max(maxX[a], maxX[b]);
        minY[a] = min(minY[a], minY[b]);
        maxY[a] = max(maxY[a], maxY[b]);
    }
    
    void activate(int x, int y) {
        // cout << x << ' ' << y << '\n';
        active[y + x*c] = true;
        // cout << y + x*c << '\n';
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(0 <= nx && nx < r && 0 <= ny && ny < c) merge(x, y, nx, ny);
        }
    }

    void check(int x, int y, ll &an) {
        int q = parent(y + x*c);
        // cout << x << ' ' << y << '\n';
        // cout << y + x*c << ' ' << parent(y + x*c) << '\n';
        // cout << sz[q] << '\n';
        // cout << minX[q] << ' ' << maxX[q] << ' ' << minY[q] << ' ' << maxY[q] << '\n'; 
        // cout << (maxX[q] - minX[q] + 1) * (maxY[q] - minY[q] + 1) << '\n';
        // cout << active[q] << ' ' << invalid[q] << '\n';
        if(active[q]) if(sz[q] == (maxX[q] - minX[q] + 1) * (maxY[q] - minY[q] + 1)) if(!invalid[q]) {
            // cout << "add!\n";
            an++;
        }
        // cout << '\n';
    }
};

struct Element{
    int val, x, y;

    Element(int a, int b, int c): val(a), x(b), y(c) {};

    bool operator<(const Element &other) const {
        return val < other.val;
    }
};

ll count_rectangles(vector<vector<int>> arr) {
    r = size(arr);
    c = size(arr[0]);

    n = r*c;

    vector<Element> a;
    for(int i = 0; i < c; i++) {
        for(int j = 0; j < r; j++) {
            a.push_back(Element(arr[j][i], j, i));
        }
    }

    sort(a.begin(), a.end());

    DSU dsutree;

    ll ans = 0;
    for(int i = 0; i < n; i++) {

        if(i) if(a[i].val != a[i-1].val) {

            set<int> checked;

            for(int x = 0; x < r; x++) {
                for(int y = 0; y < c; y++) {
                    if(dsutree.parent(y + x*c) == y + x*c) if(checked.find(y + x*c) == checked.end()) {
                        dsutree.check(x, y, ans);
                        checked.emplace(y + x*c);
                    }
                }
            }

        }

        dsutree.activate(a[i].x, a[i].y);
    }
    set<int> checked;
    for(int x = 0; x < r; x++) {
        for(int y = 0; y < c; y++) {
            if(dsutree.parent(y + x*c) == y + x*c) if(checked.find(y + x*c) == checked.end()) {
                dsutree.check(x, y, ans);
                checked.emplace(y + x*c);
            }
        }
    }

    return ans;
}

• 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