Submission #692495

#	Time	Username	Problem	Language	Result	Execution time	Memory
692495		sharaelong	Rectangles (IOI19_rect)	C++17	23 / 100	1785 ms	534036 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

struct DisjointSet {
    int n;
    vector<int> parent, rank;
    DisjointSet(int _n) : n(_n) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        rank.resize(n, 0);
    }

    int find(int u) {
        return parent[u] = (u == parent[u] ? u : find(parent[u]));
    }

    void merge(int u, int v) {
        u = find(u); v = find(v);
        if (u == v) return;
        if (rank[u] > rank[v]) swap(u, v);
        parent[u] = v;
        if (rank[u] == rank[v]) ++rank[v];
    }
};

const int MAX_N = 2500 + 1;

vector<int> row_conds[MAX_N][MAX_N];
vector<int> col_conds[MAX_N][MAX_N];
pii row_range[MAX_N][MAX_N]; // in the same row
pii col_range[MAX_N][MAX_N]; // in the same col

ll count_rectangles(vector<vector<int>> a) {
	int n = a.size();
    int m = a[0].size();
    memset(row_range, -1, sizeof row_range);
    memset(col_range, -1, sizeof col_range);
    
    for (int i=1; i+1<n; ++i) {
        vector<pii> st;
        for (int j=0; j<m; ++j) {
            while (!st.empty() && st.back().first < a[i][j]) {
                row_range[i][st.back().second].second = j-1;
                st.pop_back();
            }
            st.push_back({ a[i][j], j });
        }
        st.clear();
        for (int j=m-1; j>=0; --j) {
            while (!st.empty() && st.back().first < a[i][j]) {
                row_range[i][st.back().second].first = j+1;
                st.pop_back();
            }
            st.push_back({ a[i][j], j });
        }
    }
    for (int i=1; i+1<m; ++i) {
        vector<pii> st;
        for (int j=0; j<n; ++j) {
            while (!st.empty() && st.back().first < a[j][i]) {
                col_range[st.back().second][i].second = j-1;
                st.pop_back();
            }
            st.push_back({ a[j][i], j });
        }
        st.clear();
        for (int j=n-1; j>=0; --j) {
            while (!st.empty() && st.back().first < a[j][i]) {
                col_range[st.back().second][i].first = j+1;
                st.pop_back();
            }
            st.push_back({ a[j][i], j });
        }
    }

    for (int i=1; i+1<n; ++i) {
        for (int j=1; j+1<m; ++j) {
            auto[a, b] = row_range[i][j];
            if (a != -1 && b != -1) row_conds[a][b].push_back(i);
        }
    }
    for (int j=1; j+1<m; ++j) {
        for (int i=1; i+1<n; ++i) {
            auto[c, d] = col_range[i][j];
            if (c != -1 && d != -1) col_conds[c][d].push_back(j);
        }
    }
    for (int i=0; i<MAX_N; ++i) {
        for (int j=i; j<MAX_N; ++j) {
            row_conds[i][j].erase(unique(row_conds[i][j].begin(), row_conds[i][j].end()), row_conds[i][j].end());
            col_conds[i][j].erase(unique(col_conds[i][j].begin(), col_conds[i][j].end()), col_conds[i][j].end());
        }
    }

    DisjointSet dsu(n*m);
    for (int i=1; i+1<n; ++i) {
        for (int j=1; j+1<m; ++j) {
            if (i+2 < n) {
                if (row_range[i][j] == row_range[i+1][j] && col_range[i][j] == col_range[i+1][j]) dsu.merge(i*m+j, (i+1)*m+j);
            }
            if (j+2 < m) {
                if (row_range[i][j] == row_range[i][j+1] && col_range[i][j] == col_range[i][j+1]) dsu.merge(i*m+j, i*m+j+1);
            }
        }
    }

    ll ans = 0;
    for (int i=1; i+1<n; ++i) {
        for (int j=1; j+1<m; ++j) {
            if (i*m+j == dsu.find(i*m+j)) {
                auto[a, b] = row_range[i][j];
                auto[c, d] = col_range[i][j];
                if (a != -1 && b != -1 && c != -1 && d != -1) {
                    auto row_lb = lower_bound(row_conds[a][b].begin(), row_conds[a][b].end(), c);
                    auto row_ub = lower_bound(row_conds[a][b].begin(), row_conds[a][b].end(), d);
                    auto col_lb = lower_bound(col_conds[c][d].begin(), col_conds[c][d].end(), a);
                    auto col_ub = lower_bound(col_conds[c][d].begin(), col_conds[c][d].end(), b);
                    // cout << i << ' ' << j << ' ' << *row_lb << ' ' << *row_ub << ' ' << *col_lb << ' ' << *col_ub << endl;
                    if (*row_lb == c && *row_ub == d && row_ub-row_lb == d-c
                        && *col_lb == a && *col_ub == b && col_ub-col_lb == b-a) ans++;
                }
            }
        }
    }
    return ans;
}

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