Submission #1209565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209565		jer033	Rectangles (IOI19_rect)	C++20	59 / 100	4142 ms	1114112 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 9'900'000;

vector<int> lo_range;
vector<int> hi_range;

struct dset
{
    set<int> regular;
    set<int> inverted;

    void insert_both(int a)
    {
        regular.insert(a);
        inverted.insert(0-a);
    }

    void get_range(int a)
    {
        int hi = *(regular.upper_bound(a));
        int lo = 0-*(inverted.upper_bound(0-a));
        lo_range[a] = lo;
        hi_range[a] = hi;
    }

    dset(int a, int b)
    {
        regular = {};
        inverted = {};
        insert_both(a);
        insert_both(b);
    }

    void process_same_height(vector<int> (&x))
    {
        for (int a: x)
            get_range(a);
        for (int a: x)
            insert_both(a);
    }
};

struct cell
{
    int r;
    int c;
    int lor, hir;
    int loc, hic;
    vector<int> rbased;
    vector<int> cbased;
    bool valid;

    void update()
    {
        rbased = {lor, hir, c, r};
        cbased = {loc, hic, r, c};
        valid = 1;
    }

    void check_validity_r(int min_r, int max_r)
    {
        if (lor < (min_r-1))
        {
            valid = 0;
            //cout << r << ' ' << c << " disqualified by check_validity_r\n";
        }
        if (hir > (max_r+1))
        {
            valid = 0;
            //cout << r << ' ' << c << " disqualified by check_validity_r\n";
        }
    }

    void check_validity_c(int min_c, int max_c)
    {
        if (loc < (min_c-1))
        {
            valid = 0;
            //cout << r << ' ' << c << " disqualified by check_validity_c\n";
        }
        if (hic > (max_c+1))
        {
            valid = 0;
            //cout << r << ' ' << c << " disqualified by check_validity_c\n";
        }
    }
};

vector<vector<cell>> grid;

void c_process(vector<vector<int>> (&x))
{
    int siz = x.size();
    x.push_back({-1, -1, INF, INF, -1, -1});
    int curr_l = 0;
    int curr_r = 0;
    for (int i=1; i<=siz; i++)
    {
        if ((x[i][2] - x[i-1][2]) <= 1)
            curr_r = i;
        else
        {
            int range_l = x[curr_l][2];
            int range_r = x[curr_r][2];
            for (int j=curr_l; j<=curr_r; j++)
                grid[x[j][2]][x[j][3]].check_validity_r(range_l, range_r);
            curr_l = i;
            curr_r = i;
        }
    }
}

void r_process(vector<vector<int>> (&x))
{
    int siz = x.size();
    x.push_back({-1, -1, INF, INF, -1, -1});
    int curr_l = 0;
    int curr_r = 0;
    for (int i=1; i<=siz; i++)
    {
        if ((x[i][2] - x[i-1][2]) <= 1)
            curr_r = i;
        else
        {
            int range_l = x[curr_l][2];
            int range_r = x[curr_r][2];
            for (int j=curr_l; j<=curr_r; j++)
                grid[x[j][3]][x[j][2]].check_validity_c(range_l, range_r);
            curr_l = i;
            curr_r = i;
        }
    }
}

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

    //phase 1: fill the grid of cells with the info i need
    grid = vector<vector<cell>> (n, vector<cell> (m));
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
        {
            grid[i][j].r=i;
            grid[i][j].c=j;
        }
    
    for (int row = 0; row<n; row++)
    {
        dset worker(-1, m);
        vector<pair<int, int>> row_heights;
        for (int j = 0; j<m; j++)
            row_heights.push_back({a[row][j], j});
        sort(row_heights.begin(), row_heights.end(), greater<pair<int, int>>());
        row_heights.push_back({-1, -1});
        lo_range = vector<int> (m);
        hi_range = vector<int> (m);
        vector<int> to_insert = {row_heights[0].second};
        for (int k=1; k<=m; k++)
        {
            if (row_heights[k-1].first == row_heights[k].first)
                to_insert.push_back(row_heights[k].second);
            else
            {
                worker.process_same_height(to_insert);
                to_insert = {row_heights[k].second};
            }
        }
        
        for (int j = 0; j<m; j++)
        {
            grid[row][j].loc = lo_range[j];
            grid[row][j].hic = hi_range[j];
        }
    }

    for (int col = 0; col<m; col++)
    {
        dset worker(-1, n);
        vector<pair<int, int>> col_heights;
        for (int i = 0; i<n; i++)
            col_heights.push_back({a[i][col], i});
        sort(col_heights.begin(), col_heights.end(), greater<pair<int, int>>());
        col_heights.push_back({-1, -1});
        lo_range = vector<int> (n);
        hi_range = vector<int> (n);
        vector<int> to_insert = {col_heights[0].second};
        for (int k=1; k<=n; k++)
        {
            if (col_heights[k-1].first == col_heights[k].first)
                to_insert.push_back(col_heights[k].second);
            else
            {
                worker.process_same_height(to_insert);
                to_insert = {col_heights[k].second};
            }
        }
        
        for (int i = 0; i<n; i++)
        {
            grid[i][col].lor = lo_range[i];
            grid[i][col].hir = hi_range[i];
        }
    }

    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
        {
            grid[i][j].update();
            cell x = grid[i][j];
            //cout << x.r << ' ' << x.c << ' ' << x.lor << ' ' << x.hir << ' ' << x.loc << ' ' << x.hic << '\n';
        }

    //phase 2
    vector<vector<int>> cbasedlist;
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
            cbasedlist.push_back(grid[i][j].cbased);
    sort(cbasedlist.begin(), cbasedlist.end());
    cbasedlist.push_back({-1, -1, -1, -1});

    vector<vector<int>> to_process = {cbasedlist[0]};

    for (int ij = 1; ij <= (m*n); ij++)
    {
        if ((cbasedlist[ij][0]==cbasedlist[ij-1][0]) and (cbasedlist[ij][1]==cbasedlist[ij-1][1]))
            to_process.push_back(cbasedlist[ij]);
        else
        {
            c_process(to_process);
            to_process = {cbasedlist[ij]};
        }
    }

    vector<vector<int>> rbasedlist;
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
            rbasedlist.push_back(grid[i][j].rbased);
    sort(rbasedlist.begin(), rbasedlist.end());
    rbasedlist.push_back({-1, -1, -1, -1});

    to_process = {rbasedlist[0]};

    for (int ij = 1; ij <= (m*n); ij++)
    {
        if ((rbasedlist[ij][0]==rbasedlist[ij-1][0]) and (rbasedlist[ij][1]==rbasedlist[ij-1][1]))
            to_process.push_back(rbasedlist[ij]);
        else
        {
            r_process(to_process);
            to_process = {rbasedlist[ij]};
        }
    }

    //finding answer
    set<vector<int>> valid_rectangles;
    for (int i=1; i<(n-1); i++)
        for (int j=1; j<(m-1); j++)
        {
            cell x = grid[i][j];
            if (x.valid and (x.lor!=-1) and (x.hir!=n) and (x.loc!=-1) and (x.hic!=m))
            {
                valid_rectangles.insert({x.lor, x.hir, x.loc, x.hic});
                //cout << x.lor << ' ' << x.hir << ' ' << x.loc << ' ' << x.hic << '\n';
            }
        }
    long long answer = valid_rectangles.size();

	return answer;
}

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