Submission #281580

#	Time	Username	Problem	Language	Result	Execution time	Memory
281580		stoyan_malinin	Rectangles (IOI19_rect)	C++14	13 / 100	1797 ms	944304 KiB

rect

#include "rect.h"
//#include "grader.cpp"

#include <stack>
#include <deque>
#include <vector>
#include <assert.h>
#include <iostream>
#include <functional>

using namespace std;

const int MAXN = 2505;
const int MAXLog = 15;

struct FenwickTree
{
    vector <int> tree;

    FenwickTree(){}
    FenwickTree(int n)
    {
        this->tree.assign(n+5, 0);
    }

    void update(int ind, int val)
    {
        ind++;
        while(ind<tree.size())
        {
            tree[ind] += val;
            ind += ind&(-ind);
        }
    }

    int query(int ind)
    {
        ind++;
        int sum = 0;

        while(ind>0)
        {
            sum += tree[ind];
            ind -= ind&(-ind);
        }

        return sum;
    }
};

int n, m;
int a[MAXN][MAXN];

int helpRotate[MAXN][MAXN];
void rotate90()
{
    for(int j = 0;j<m;j++)
        for(int i = n-1;i>=0;i--)
            helpRotate[j][n - 1 - i] = a[i][j];

    swap(n, m);
    for(int i = 0;i<n;i++)
        for(int j = 0;j<m;j++)
        a[i][j] = helpRotate[i][j];
}

int rightBad[MAXN][MAXN], leftBad[MAXN][MAXN];
short int downBad[MAXN][MAXN][20], upBad[MAXN][MAXN][20];

int logVal[MAXN];

void initSparse(short int sparse[MAXN][MAXN][20], int row, int mode)
{
    for(int step = 1;step<=MAXLog;step++)
    {
        for(int j = 0;j<m;j++)
        {
            if(j+(1<<(step-1))<m)
            {
                if(mode==0)
                    sparse[row][j][step] = min(sparse[row][j][step-1], sparse[row][j+(1<<(step-1))][step-1]);
                else
                    sparse[row][j][step] = max(sparse[row][j][step-1], sparse[row][j+(1<<(step-1))][step-1]);
            }
            else
            {
                sparse[row][j][step] = sparse[row][j][step-1];
            }
        }
    }
}

void init()
{
    //if(n<m) rotate90();

    logVal[0] = logVal[1] = 0;
    for(int i = 2;i<=max(n, m)+2;i++)
    {
        logVal[i] = logVal[i/2] + 1;
    }

    for(int i = 0;i<n;i++)
    {
        stack <int> st;
        for(int j = 0;j<m;j++)
        {
            while(st.empty()==false && a[i][st.top()]<a[i][j]) st.pop();
            leftBad[i][j] = ((st.empty()==true)?-1:st.top());

            st.push(j);
        }

        while(st.empty()==false) st.pop();
        for(int j = m-1;j>=0;j--)
        {
            while(st.empty()==false && a[i][st.top()]<a[i][j]) st.pop();
            rightBad[i][j] = ((st.empty()==true)?m-1:st.top());

            st.push(j);
        }
    }

    for(int j = 0;j<m;j++)
    {
        stack <int> st;
        for(int i = 0;i<n;i++)
        {
            while(st.empty()==false && a[st.top()][j]<a[i][j]) st.pop();
            upBad[i][j][0] = ((st.empty()==true)?-1:st.top());

            st.push(i);
        }

        while(st.empty()==false) st.pop();
        for(int i = n-1;i>=0;i--)
        {
            while(st.empty()==false && a[st.top()][j]<a[i][j]) st.pop();
            downBad[i][j][0] = ((st.empty()==true)?n-1:st.top());

            st.push(i);
        }
    }

    for(int row = 0;row<n;row++)
    {
        initSparse(downBad, row, 0);
        initSparse(upBad, row, 1);
    }
}

int getVal(int row, int l, int r, short int sparse[MAXN][MAXN][20], int mode)
{
    int log2 = logVal[r-l+1];

    if(mode==0)
    {
        if(l>r) return n;
        return min(sparse[row][l][log2], sparse[row][r-(1<<log2)+1][log2]);
    }
    else
    {
        if(l>r) return -1;
        return max(sparse[row][l][log2], sparse[row][r-(1<<log2)+1][log2]);
    }
}

vector <int> toRemove[MAXN];
long long evalRowSeq(int lRow, int rRow, int c1, int c2)
{
    if(lRow>rRow) return 0;

    FenwickTree T(n);
    for(int row = rRow;row>=lRow;row--)
    {
        toRemove[row].clear();
    }

    int ans = 0;
    for(int row = rRow;row>=lRow;row--)
    {
        int maxRow = getVal(row-1, c1+1, c2-1, downBad, 0);

        T.update(row, +1);
        toRemove[getVal(row+1, c1+1, c2-1, upBad, 1)].push_back(row);

        for(int x: toRemove[row]) T.update(x, -1);

        ans += T.query(min(maxRow-1, rRow));
        //if(c1==0 && c2==2) cout << "add " << row << " until " << getVal(row+1, c1+1, c2-1, upBad, 1) << '\n';
    }

    return ans;
}

long long evalN3log()
{
    long long answer = 0;
    for(int c1 = 0;c1<m;c1++)
    {
        for(int c2 = c1+2;c2<m;c2++)
        {
            int ind = 1;
            while(ind<n-1)
            {
                int l = ind;
                while(ind<n-1 && rightBad[ind][c1]>=c2 && leftBad[ind][c2]<=c1) ind++;

                answer += evalRowSeq(l, ind-1, c1, c2);
                ind++;
            }
        }
    }

    return answer;
}

short int downOne[MAXN][MAXN][20];
int leftZero[MAXN][MAXN], rightZero[MAXN][MAXN], downZero[MAXN][MAXN];

void init01()
{
    logVal[0] = logVal[1] = 0;
    for(int i = 2;i<=max(n, m)+2;i++)
    {
        logVal[i] = logVal[i/2] + 1;
    }

    for(int i = 0;i<n;i++)
    {
        int zero = -1;
        for(int j = 0;j<m;j++)
        {
            if(a[i][j]==0) zero = j;
            leftZero[i][j] = zero;
        }

        zero = m;
        for(int j = m-1;j>=0;j--)
        {
            if(a[i][j]==0) zero = j;
            rightZero[i][j] = zero;
        }
    }

    for(int j = 0;j<m;j++)
    {
        int one = n, zero = n;
        for(int i = n-1;i>=0;i--)
        {
            if(a[i][j]==1) one = i;
            if(a[i][j]==0) zero = i;

            downOne[i][j][0] = one;
            downZero[i][j] = zero;
        }
    }

    for(int row = 0;row<n;row++)
        initSparse(downOne, row, 0);
}

long long eval01()
{
    init01();

    function <bool(int, int, int)> eval = [&](int l, int r, int row)
    {
        if(l+1>=r) return false;

        int oneRow = getVal(row+1, l+1, r-1, downOne, 0);
        if(oneRow>=n) return false;

        //cout << oneRow << '\n';
        if(downZero[row+1][l]<oneRow) return false;
        if(downZero[row+1][r]<oneRow) return false;

        //cout << "ok" << '\n';
        if(rightZero[row][l+1]<=r-1) return false;
        if(rightZero[oneRow][l+1]<=r-1) return false;

        return true;
    };

    int answer = 0;
    for(int i = 0;i<n-2;i++)
    {
        int last = -1;
        for(int j = 0;j<m;j++)
        {
            if(a[i+1][j]==1)
            {
                if(last==-1)
                {
                    last = j;
                    continue;
                }

                //cout << i << " -> " << last << " " << j << '\n';

                answer += eval(last, j, i);
                last = j;
            }
        }
    }

    return answer;
}

long long count_rectangles(vector<vector<int>> _a)
{
    n = _a.size();
    m = _a[0].size();
    for(int i = 0;i<n;i++)
        for(int j = 0;j<m;j++)
            a[i][j] = _a[i][j];

    init();

    //return evalN3log();
    return eval01();

    /*
    cout << '\n';
    for(int i = 0;i<n;i++)
    {
        for(int j = 0;j<m;j++) cout << a[i][j] << " ";
        cout << '\n';
    }
    cout << '\n';

    cout << '\n';
    for(int i = 0;i<n;i++)
    {
        for(int j = 0;j<m;j++) cout << downBad[i][j][0] << " ";
        cout << '\n';
    }
    cout << '\n';
    */


}
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6

4 4
1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1

4 5
1 1 1 0 1
1 0 1 1 1
1 1 1 0 1
1 1 1 1 1

2 2
1 1
1 1

3 3
1 1 1
1 1 1
1 0 1

5 5
1 1 1 1 1
1 1 1 1 1
1 1 0 1 1
1 1 1 1 1
1 1 1 1 1
*/

Compilation message (stderr)

rect.cpp: In member function 'void FenwickTree::update(int, int)':
rect.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         while(ind<tree.size())
      |               ~~~^~~~~~~~~~~~

• 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