Submission #571284

#	Time	Username	Problem	Language	Result	Execution time	Memory
571284		azberjibiou	Rectangles (IOI19_rect)	C++17	37 / 100	5090 ms	39264 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
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;
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;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
    N=a.size();
    M=a[0].size();
    for(int i=1;i<N-1;i++)
    {
        for(int j=1;j<M-1;j++)
        {
            int u=i, d=i, l=j, r=j;
            while(u!=-1 && a[u][j]<=a[i][j])    u--;
            while(d!=N && a[d][j]<=a[i][j]) d++;
            while(l!=-1 && a[i][l]<=a[i][j])    l--;
            while(r!=M && a[i][r]<=a[i][j]) r++;
            if(u!=-1 && d!=N && l!=-1 && r!=M)  v.emplace_back(u+1, d-1, l+1, r-1);
        }
    }
    sort(v.begin(), v.end(), cmp1);
    v.erase(unique(v.begin(), v.end()), v.end());
    int ans=0;
    for(auto ele : v)
    {
        bool ok=true;
        for(int i=ele.x1;i<=ele.x2;i++)
        {
            for(int j=ele.y1;j<=ele.y2;j++)
            {
                if(a[ele.x1-1][j]<=a[i][j] || a[ele.x2+1][j]<=a[i][j] || a[i][ele.y1-1]<=a[i][j] || a[i][ele.y2+1]<=a[i][j])
                    ok=false;
            }
        }
        if(ok)  ans++;
    }
	return ans;
}

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