Submission #1202283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202283		LucaIlie	Rectangles (IOI19_rect)	C++20	0 / 100	1 ms	840 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2500;
const int MAX_CELLS = MAX_N * MAX_N;
int dl[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};
bool active[MAX_CELLS];
bool frecv[MAX_CELLS];
int parent[MAX_CELLS];
int bad[MAX_CELLS];
int sizee[MAX_CELLS];
int minL[MAX_CELLS];
int minC[MAX_CELLS];
int maxC[MAX_CELLS];
int maxL[MAX_CELLS];

int findParent(int x) {
    if (parent[x] != x)
        parent[x] = findParent(parent[x]);
    return parent[x];
}

void connect(int x, int y) {
    x = findParent(x);
    y = findParent(y);
    if (x == y)
        return;

    sizee[x] += sizee[y];
    bad[x] += bad[y];
    minL[x] = min(minL[x], minL[y]);
    maxL[x] = max(maxL[x], maxL[y]);
    minC[x] = min(minC[x], minC[y]);
    maxC[x] = max(maxC[x], maxC[y]);
}

bool check(int p) {
    if (bad[p])
        return false;

    int area = (maxL[p] - minL[p] + 1) * (maxC[p] - minC[p] + 1);
    return (sizee[p] == area);
    
}

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

    vector<pair<int, pair<int, int>>> sortedCells;
    for (int l = 0; l < n; l++) {
        for (int c = 0; c < m; c++) 
            sortedCells.push_back({a[l][c], {l, c}});
    }
    sort(sortedCells.begin(), sortedCells.end());

    int ans = 0;
    for (int l = 0; l < n; l++) {
        for (int c = 0; c < m; c++) {
            int id = l * m + c;
            sizee[id] = 1;
            parent[id] = id;
            minL[id] = maxL[id] = l;
            minC[id] = maxC[id] = c;
            bad[id] = (l == 0 || c == 0 || l == n - 1 || c == m - 1);
            //printf("%d ", a[l][c]);
        }
        //printf("\n");
    }
    
    int ind1 = 0;
    while (ind1 < n * m) {
        int ind2 = ind1;
        int val = a[sortedCells[ind1].second.first][sortedCells[ind1].second.second];
        while (ind2 < n * m && a[sortedCells[ind2].second.first][sortedCells[ind2].second.second] == val)
            ind2++;

        for (int i = ind1; i < ind2; i++) {
            int l = sortedCells[i].second.first;
            int c = sortedCells[i].second.second;
            int id = l * m + c;
            for (int d = 0; d < 4; d++) {
                int newL = l + dl[d];
                int newC = c + dc[d];
                int newId = newL * m + newC;
                if (active[newId])
                    connect(id, newId);
            }
            active[id] = true;
        }

        for (int i = ind1; i < ind2; i++) {
            int l = sortedCells[i].second.first;
            int c = sortedCells[i].second.second;
            int id = l * m + c;
            int p = findParent(id);
            if (frecv[p])
                continue;

            frecv[p] = 1;
            if (check(p))
                ans++;

//            if (check(p))
//                printf("%d %d %d\n", l, c, a[l][c]);
        }
        for (int i = ind1; i < ind2; i++) {
            int l = sortedCells[i].second.first;
            int c = sortedCells[i].second.second;
            int id = l * m + c;
            int p = findParent(id);
            frecv[p] = 0;
        }
        
        ind1 = ind2;
    }

    return ans;
}

• 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