Submission #1292522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292522		MMihalev	Rectangles (IOI19_rect)	C++20	10 / 100	13 ms	25956 KiB

rect

#include<iostream>
#include<vector>
#include<stack>
#include "rect.h"
using namespace std;
const int MAX_N=2510;
long long count_rectangles(std::vector<std::vector<int> > a)
{
    int n=a.size();
    int m=a[0].size();
    long long ans=0;

    for(int i=1;i<a.size()-1;i++)
    {
        vector<int>colmax,p;
        colmax.resize(m);
        p.resize(m);

        vector<vector<int>>cnt;
        cnt.resize(m);
        for(int j=0;j<m;j++)cnt[j].resize(m);

        for(int j=i;j<a.size()-1;j++)
        {
            vector<vector<bool>>ok;
            ok.resize(m);
            for(int j=0;j<m;j++)ok[j].resize(m);


            for(int col=1;col<m-1;col++)
            {
                colmax[col]=max(colmax[col],a[j][col]);
                if(colmax[col]<min(a[i-1][col],a[j+1][col]))
                {
                    p[col]=1;
                }
                else p[col]=0;

                p[col]+=p[col-1];
            }

            stack<int>s;
            s.push(m-1);
            for(int col=m-2;col>=0;col--)
            {
                while(s.size() && a[j][s.top()]<a[j][col])s.pop();

                if(s.size())
                {
                    if(col+1<=s.top()-1)
                    {
                        if(!ok[col+1][s.top()-1])
                        {
                            ok[col+1][s.top()-1]=1;
                            cnt[col+1][s.top()-1]++;
                            if(cnt[col+1][s.top()-1]==j-i+1 && p[s.top()-1]-p[col]==s.top()-1-col)
                            {
                                ans++;
                            }
                        }

                    }
                }

                s.push(col);
            }

            while(s.size())s.pop();
            s.push(0);
            for(int col=1;col<m;col++)
            {
                while(s.size() && a[j][s.top()]<=a[j][col])s.pop();

                if(s.size())
                {
                    if(s.top()+1<=col-1)
                    {
                        if(!ok[s.top()+1][col-1])
                        {
                            ok[s.top()+1][col-1]=1;
                            cnt[s.top()+1][col-1]++;
                            if(cnt[s.top()+1][col-1]==j-i+1 && p[col-1]-p[s.top()]==col-1-s.top())
                            {
                                ans++;
                            }
                        }

                    }
                }

                s.push(col);
            }
        }
    }

	return ans;
}

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