Submission #203533

#	Time	Username	Problem	Language	Result	Execution time	Memory
203533		stefdasca	Rectangles (IOI19_rect)	C++14	100 / 100	2348 ms	424868 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
using namespace std;int maxst[2502][2502], maxdr[2502][2502], maxup[2502][2502], maxdwn[2502][2502];
int upleft[2502][2502], downleft[2502][2502], leftup[2502][2502], rightup[2502][2502];

vector<long long> v;
void check(int xa, int xb, int ya, int yb)
{
	if(xb < xa || yb < ya)
        return;
	if(!((maxdr[xb][ya-1]-1 == yb && rightup[xb][ya-1] <= xa) || (maxst[xb][yb+1]+1 == ya && leftup[xb][yb+1] <= xa)))
        return;
	if(!((maxdwn[xa-1][yb]-1 == xb && downleft[xa-1][yb] <= ya) || (maxup[xb+1][yb]+1 == xa && upleft[xb+1][yb] <= ya)))
        return;
	v.push_back(((1LL * xa * 3010 + xb) * 3010 + ya) * 3010 + yb);
}
long long count_rectangles(vector<vector<int> > a)
{
    int n = a.size();
    int m = a[0].size();
    long long ans = 0;
    deque<int> d;
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < m; ++j)
        {
            while(!d.empty() && a[i][j] > a[i][d.back()])
                d.pop_back();
            if(d.empty())
                maxst[i][j] = -1;
            else
                maxst[i][j] = d.back();
            d.push_back(j);
        }
        d.clear();
        for(int j = m - 1; j >= 0; --j)
        {
            while(!d.empty() && a[i][j] > a[i][d.back()])
                d.pop_back();
            if(d.empty())
                maxdr[i][j] = -1;
            else
                maxdr[i][j] = d.back();
            d.push_back(j);
        }
        d.clear();
    }
    for(int i = 0; i < m; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            while(!d.empty() && a[j][i] > a[d.back()][i])
                d.pop_back();
            if(d.empty())
                maxup[j][i] = -1;
            else
                maxup[j][i] = d.back();
            d.push_back(j);
        }
        d.clear();
        for(int j = n-1; j >= 0; --j)
        {
            while(!d.empty() && a[j][i] > a[d.back()][i])
                d.pop_back();
            if(d.empty())
                maxdwn[j][i] = -1;
            else
                maxdwn[j][i] = d.back();
            d.push_back(j);
        }
        d.clear();
    }
    for(int j = 0; j < m; ++j)
    {
        for(int i = 0; i < n; ++i)
        {
            if(maxup[i][j] != -1)
            {
                if(j > 0 && maxup[i][j] == maxup[i][j-1])
                    upleft[i][j] = upleft[i][j-1];
                else
                    if(j > 0 && i == maxdwn[maxup[i][j]][j-1])
                        upleft[i][j] = downleft[maxup[i][j]][j-1];
                    else
                        upleft[i][j] = j;
            }
            if(maxdwn[i][j] != -1)
            {
                if(j > 0 && maxdwn[i][j] == maxdwn[i][j-1])
                    downleft[i][j] = downleft[i][j-1];
                else
                    if(j > 0 && i == maxup[maxdwn[i][j]][j-1])
                        downleft[i][j] = upleft[maxdwn[i][j]][j-1];
                    else
                        downleft[i][j] = j;
            }
        }
    }
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < m; ++j)
        {
            if(maxst[i][j] != -1)
            {
                if(i > 0 && maxst[i][j] == maxst[i-1][j])
                    leftup[i][j] = leftup[i-1][j];
                else
                    if(i > 0 && j == maxdr[i-1][maxst[i][j]])
                        leftup[i][j] = rightup[i-1][maxst[i][j]];
                    else
                        leftup[i][j] = i;
            }
            if(maxdr[i][j] != -1)
            {
                if(i > 0 && maxdr[i][j] == maxdr[i-1][j])
                    rightup[i][j] = rightup[i-1][j];
                else
                    if(i > 0 && j == maxst[i-1][maxdr[i][j]])
                        rightup[i][j] = leftup[i-1][maxdr[i][j]];
                    else
                        rightup[i][j] = i;
            }
        }
    }
    for(int i = 1; i + 1 < n; ++i)
        for(int j = 1; j + 1 < m; ++j)
        {
            if(maxup[i+1][j] != -1 && maxst[i][j+1] != -1)
                check(maxup[i+1][j]+1, i, maxst[i][j+1]+1, j);
            if(maxup[i+1][j] != -1 && maxdr[i][j-1] != -1)
                check(maxup[i+1][j]+1, i, j, maxdr[i][j-1]-1);
            if(maxdwn[i-1][j] != -1 && maxst[i][j+1] != -1)
                check(i, maxdwn[i-1][j]-1, maxst[i][j+1]+1, j);
            if(maxdwn[i-1][j] != -1 && maxdr[i][j-1] != -1)
                check(i, maxdwn[i-1][j]-1, j, maxdr[i][j-1]-1);
            if(maxdwn[i-1][j] != -1 && maxdr[maxdwn[i-1][j]-1][j-1] != -1)
                check(i, maxdwn[i-1][j]-1, j, maxdr[maxdwn[i-1][j]-1][j-1]-1);
            if(maxdwn[i-1][j] != -1 && maxst[maxdwn[i-1][j]-1][j+1] != -1)
                check(i, maxdwn[i-1][j]-1, maxst[maxdwn[i-1][j]-1][j+1]+1, j);
        }
    sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
    return v.size();
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:21:15: warning: unused variable 'ans' [-Wunused-variable]
     long long ans = 0;
               ^~~

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