oj.uz

Submission #280507

# Submission time Handle Problem Language Result Execution time Memory
280507 2020-08-22T21:02:18 Z stoyan_malinin Rectangles (IOI19_rect) C++14
0 / 100
 54 ms 63616 KB 
#include "rect.h"
//#include "grader.cpp"

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

using namespace std;

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

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];
int downBad[MAXN][MAXN][20], upBad[MAXN][MAXN][20];

int logVal[MAXN];

void initSparse(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<=n;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, 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]);
    }
}

long long evalRowSeq(int lRow, int rRow, int c1, int c2)
{
    if(lRow>rRow) return 0;

    int ans = 0;
    for(int row = lRow;row<=rRow;row++)
    {
        int maxRow = getVal(row-1, c1+1, c2-1, downBad, 0);
        for(int row1 = row;row1<maxRow;row1++)
        {
            assert(c1>=0 && c2<m && row>=1 && row1<n-1);
            if(getVal(row1+1, c1+1, c2-1, upBad, 1)<row) ans++;
        }
    }

    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;
}

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();

    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
*/

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1024 KB Output is correct
4 Correct 1 ms 1152 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Incorrect 1 ms 1152 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1024 KB Output is correct
4 Correct 1 ms 1152 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Incorrect 1 ms 1152 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1024 KB Output is correct
4 Correct 1 ms 1152 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Incorrect 1 ms 1152 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1024 KB Output is correct
4 Correct 1 ms 1152 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Incorrect 1 ms 1152 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 63616 KB Output is correct
2 Correct 44 ms 54008 KB Output is correct
3 Correct 35 ms 63608 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Incorrect 32 ms 63616 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1024 KB Output is correct
4 Correct 1 ms 1152 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Incorrect 1 ms 1152 KB Output isn't correct
7 Halted 0 ms 0 KB -