제출 #571371

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
571371		azberjibiou	Rectangles (IOI19_rect)	C++17	72 / 100	5027 ms	329840 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
const int mxN=2505;
typedef struct rect{
    int x1, x2, y1, y2;
    rect() : x1(0), x2(0), y1(0), y2(0) {}
    rect(int x1, int x2, int y1, int y2) : x1(x1), x2(x2), y1(y1), y2(y2) {}
    bool operator==(rect a)
    {
        return (a.x1==x1 && a.x2==x2 && a.y1==y1 && a.y2==y2);
    }
}rect;
int N, M;
int A[mxN][mxN];
int L[mxN][mxN], R[mxN][mxN], U[mxN][mxN], D[mxN][mxN];
vector <rect> v;
bool cmp1(rect a, rect b)
{
    if(a.x1!=b.x1)  return a.x1<b.x1;
    if(a.x2!=b.x2)  return a.x2<b.x2;
    if(a.y1!=b.y1)  return a.y1<b.y1;
    return a.y2<b.y2;
}
void make_LRUD1()
{
    for(int i=1;i<N-1;i++)
    {
        stack <int> stk;
        for(int j=0;j<M;j++)
        {
            while(!stk.empty() && A[i][stk.top()]<=A[i][j])   stk.pop();
            L[i][j]=(stk.empty() ? -1 : stk.top());
            stk.push(j);
        }
        while(!stk.empty()) stk.pop();
        for(int j=M-1;j>=0;j--)
        {
            while(!stk.empty() && A[i][stk.top()]<=A[i][j])   stk.pop();
            R[i][j]=(stk.empty() ? M : stk.top());
            stk.push(j);
        }
    }
    for(int i=1;i<M-1;i++)
    {
        stack <int> stk;
        for(int j=0;j<N;j++)
        {
            while(!stk.empty() && A[stk.top()][i]<=A[j][i]) stk.pop();
            U[j][i]=(stk.empty() ? -1 : stk.top());
            stk.push(j);
        }
        while(!stk.empty()) stk.pop();
        for(int j=N-1;j>=0;j--)
        {
            while(!stk.empty() && A[stk.top()][i]<=A[j][i]) stk.pop();
            D[j][i]=(stk.empty() ? N : stk.top());
            stk.push(j);
        }
    }
}
void make_LRUD2()
{
    for(int i=1;i<N-1;i++)
    {
        stack <int> stk;
        for(int j=0;j<M;j++)
        {
            while(!stk.empty() && A[i][stk.top()]<A[i][j])   stk.pop();
            L[i][j]=(stk.empty() ? -1 : stk.top());
            stk.push(j);
        }
        while(!stk.empty()) stk.pop();
        for(int j=M-1;j>=0;j--)
        {
            while(!stk.empty() && A[i][stk.top()]<A[i][j])   stk.pop();
            R[i][j]=(stk.empty() ? M : stk.top());
            stk.push(j);
        }
    }
    for(int i=1;i<M-1;i++)
    {
        stack <int> stk;
        for(int j=0;j<N;j++)
        {
            while(!stk.empty() && A[stk.top()][i]<A[j][i]) stk.pop();
            U[j][i]=(stk.empty() ? -1 : stk.top());
            stk.push(j);
        }
        while(!stk.empty()) stk.pop();
        for(int j=N-1;j>=0;j--)
        {
            while(!stk.empty() && A[stk.top()][i]<A[j][i]) stk.pop();
            D[j][i]=(stk.empty() ? N : stk.top());
            stk.push(j);
        }
    }
}
long long count_rectangles(std::vector<std::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];
    make_LRUD1();
    for(int i=1;i<N-1;i++)
    {
        for(int j=1;j<M-1;j++)
        {
            if(U[i][j]!=-1 && D[i][j]!=N && L[i][j]!=-1 && R[i][j]!=M)  v.emplace_back(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1);
        }
    }
    sort(v.begin(), v.end(), cmp1);
    v.erase(unique(v.begin(), v.end()), v.end());
    make_LRUD2();
    int ans=0;
    for(auto ele : v)
    {
        bool ok=true;
        for(int i=ele.x1;i<=ele.x2;i++) if(R[i][ele.y1-1]<=ele.y2 || L[i][ele.y2+1]>=ele.y1)    ok=false;
        for(int i=ele.y1;i<=ele.y2;i++) if(D[ele.x1-1][i]<=ele.x2 || U[ele.x2+1][i]>=ele.x1)    ok=false;
        if(ok)  ans++;
    }
	return ans;
}

• 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: 0 / 28