Submission #1209658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209658		jer033	Rectangles (IOI19_rect)	C++20	0 / 100	791 ms	1114112 KiB

rect

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

/*
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);
    }
};*/

int convert(int a, int b)
{
    a++; b++;
    return max_n*a+b;
}

vector<int> find_lo_range(vector<int> (&x))
{
    int m = x.size();
    vector<int> ans(m);
    vector<pair<int, int>> k = {{INF, -1}};
    for (int i=0; i<m; i++)
    {
        bool done = 0;
        while (done==0)
        {
            int t = k.size(); t--;
            if (k[t].first > x[i])
            {
                done = 1;
                ans[i] = k[t].second;
            }
            else
                k.pop_back();
        }
        k.push_back({x[i], i});
    }
    return ans;
}

vector<int> find_hi_range(vector<int> (&x))
{
    int m = x.size();
    vector<int> ans(m);
    vector<pair<int, int>> k = {{INF, m}};
    for (int i=m-1; i>=0; i--)
    {
        bool done = 0;
        while (done==0)
        {
            int t = k.size(); t--;
            if (k[t].first > x[i])
            {
                done = 1;
                ans[i] = k[t].second;
            }
            else
                k.pop_back();
        }
        k.push_back({x[i], i});
    }
    return ans;
}

/*
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";
        }
    }
};*/

using cell = vector<int>;

cell cbased(cell (&a))
{
    return {a[4], a[5], a[0], a[1], a[2], a[3]};
}

cell rbased(cell (&a))
{
    return {a[2], a[3], a[1], a[0], a[4], a[5]};
}

vector<vector< cell >> grid;

vector<vector<bool>> valid;


void check_validity_r(cell (&x), int min_r, int max_r)
{
    if (x[4] < (min_r-1))
        valid[x[2]][x[3]] = 0;
    if (x[5] > (max_r+1))
        valid[x[2]][x[3]] = 0;
}

void check_validity_c(cell (&x), int min_c, int max_c)
{
    if (x[4] < (min_c-1))
        valid[x[3]][x[2]] = 0;
    if (x[5] > (max_c+1))
        valid[x[3]][x[2]] = 0;
}

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++)
                check_validity_r(x[j], range_l, range_r);
                //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++)
                check_validity_c(x[j], range_l, range_r);
                //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, vector<int> (6)));
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
        {
            grid[i][j][0]=i;
            grid[i][j][1]=j;
        }
    
    for (int row = 0; row<n; row++)
    {
        //dset worker(-1, m);
        //vector<pair<int, int>> row_heights(m);
        //for (int j = 0; j<m; j++)
            //row_heights[j] = {a[row][j], j};
        //sort(row_heights.begin(), row_heights.end(), greater<pair<int, int>>());
        //row_heights.push_back({-1, -1});
        vector<int> lo_range = find_lo_range(a[row]);//vector<int> (m);
        vector<int> hi_range = find_hi_range(a[row]);//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][4] = lo_range[j];
            grid[row][j][5] = hi_range[j];
        }
    }

    for (int col = 0; col<m; col++)
    {
        /*dset worker(-1, n);
        vector<pair<int, int>> col_heights(n);
        for (int i = 0; i<n; i++)
            col_heights[i] = {a[i][col], i};
        sort(col_heights.begin(), col_heights.end(), greater<pair<int, int>>());
        col_heights.push_back({-1, -1});*/
        vector<int> val(n);
        for (int k=0; k<n; k++)
            val[k] = a[k][col];
        vector<int> lo_range = find_lo_range(val);//vector<int> (n);
        vector<int> hi_range = find_hi_range(val);//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][2] = lo_range[i];
            grid[i][col][3] = 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
    valid = vector<vector<bool>> (n, vector<bool> (m, 1));

    vector<vector<vector<int>>> cbasedmap(INF);
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
            cbasedmap[convert(grid[i][j][4], grid[i][j][5])].push_back(cbased(grid[i][j]));
    for (int i=0; i<INF; i++)
        c_process(cbasedmap[i]);

   /* vector<vector<int>> cbasedlist;
    cbasedlist.reserve(m*n+1);
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
            cbasedlist.push_back(cbased(grid[i][j]));
    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]};
        }
    }

    cbasedlist.clear();*/

    vector<vector<vector<int>>> rbasedmap(INF);
    for (int j=0; j<m; j++)
        for (int i=0; i<n; i++)
            cbasedmap[convert(grid[i][j][2], grid[i][j][3])].push_back(rbased(grid[i][j]));
    for (int i=0; i<INF; i++)
        r_process(rbasedmap[i]);
    /*vector<vector<int>> rbasedlist;
    rbasedlist.reserve(m*n+1);
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
            rbasedlist.push_back(rbased(grid[i][j]));
    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]};
        }
    }

    rbasedlist.clear();*/

    //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 (valid[i][j] and (x[2]!=-1) and (x[3]!=n) and (x[4]!=-1) and (x[5]!=m))
            {
                valid_rectangles.insert({x[2], x[3], x[4], x[5]});
                //cout << x.lor << ' ' << x.hir << ' ' << x.loc << ' ' << x.hic << '\n';
            }
        }
    long long answer = valid_rectangles.size();

	return answer;
}

• 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