제출 #294157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
294157		Pajaraja	Rectangles (IOI19_rect)	C++17	49 / 100	2523 ms	544612 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define MAXN 2507
using namespace std;
bool dv[707][707][707],dh[707][707][707];
long long count_rectangles(std::vector<std::vector<int> > a)
{
    int n=a.size(),m=a[0].size();
    for(int i=0;i<n;i++)
    {
        stack<int> st;
        for(int j=0;j<m;j++)
        {
            while(!st.empty() && a[i][st.top()]<a[i][j]) st.pop();
            if(!st.empty()) dv[i][st.top()+1][j-1]=true;
            st.push(j);
        }
        while(!st.empty()) st.pop();
        for(int j=m-1;j>=0;j--)
        {
            while(!st.empty() && a[i][st.top()]<a[i][j]) st.pop();
            if(!st.empty()) dv[i][j+1][st.top()-1]=true;
            st.push(j);
        }
    }
    for(int i=0;i<m;i++)
    {
        stack<int> st;
        for(int j=0;j<n;j++)
        {
            while(!st.empty() && a[st.top()][i]<a[j][i]) st.pop();
            if(!st.empty()) dh[st.top()+1][j-1][i]=true;
            st.push(j);
        }
        while(!st.empty()) st.pop();
        for(int j=n-1;j>=0;j--)
        {
            while(!st.empty() && a[st.top()][i]<a[j][i]) st.pop();
            if(!st.empty()) dh[j+1][st.top()-1][i]=true;
            st.push(j);
        }
    }
    long long sol=0;
    for(int a=1;a<n;a++) for(int b=a+1;b<n;b++) for(int c=1;c<m;c++) for(int d=c+1;d<m;d++)
    {
        if(!dh[a][b-1][d-1]) break;
        bool fas=false;
        for(int i=a;i<b && !fas;i++) if(!dv[i][c][d-1]) fas=true;
        if(!fas) sol++;
    }
	return sol;
}

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