제출 #891490

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
891490		Faisal_Saqib	Rectangles (IOI19_rect)	C++17	0 / 100	5113 ms	1048576 KiB

rect

#include <vector>
#include <iostream>
using namespace std;
struct SegmentTree
{
	int mx=0;
	int s,e;
	SegmentTree* next[2];
	SegmentTree(int l,int r)
	{
		s=l;
		e=r;
		if(s!=e)
		{
			int mid=(s+e)/2;
			next[0]=new SegmentTree(s,mid);
			next[1]=new SegmentTree(mid+1,e);
		}
	}
	void insert(int& l,int& val)
	{
		if(e<l or l<s)
			return;
		mx=max(mx,val);
		if(s==e)
			return;
		next[0]->insert(l,val);
		next[1]->insert(l,val);
	}
	int get(int& l,int& r)
	{
		if(e<l or r<s)
			return 0;
		if(l<=s and e<=r)
			return mx;
		return max(next[0]->get(l,r),next[1]->get(l,r));
	}
};
long long count_rectangles(std::vector<std::vector<int> >a)
{
	long long ans=0;
	int n=a.size();
	int m=a[0].size();
	SegmentTree* fix1[n-1];
	SegmentTree* fix2[m-1];
	for(int i=1;i<=(n-2);i++)
	{
		fix1[i]=new SegmentTree(1,m-2);
		for(int j=1;j<=(m-2);j++)
		{
			fix1[i]->insert(j,a[i][j]);
		}
	}
	for(int j=1;j<=(m-2);j++)
	{
		fix2[j]=new SegmentTree(1,n-2);
		for(int i=1;i<=(n-2);i++)
		{
			fix2[j]->insert(i,a[i][j]);
		}
	}
	for(int r1=1;r1<=(n-2);r1++)
	{
		for(int c1=1;c1<=(m-2);c1++)
		{
			for(int r2=r1;r2<=(n-2);r2++)
			{
				for(int c2=c1;c2<=(m-2);c2++)
				{
					bool pos=1;
					for(int addi=0;addi<=(r2-r1) and pos;addi++)
					{
						int celli=r1+addi;
						int mi=min(a[celli][c1-1],a[celli][c2+1]);
						int fp=fix1[celli]->get(c1,c2);
						if(fp>=mi)
						{
							pos=0;
							break;
						}
					}
					for(int addj=0;addj<=(c2-c1);addj++)
					{
						int cellj=c1+addj;
						int mi=min(a[r1-1][cellj],a[r2+1][cellj]);
						int fp=fix2[cellj]->get(r1,r2);
						if(fp>=mi)
						{
							pos=0;
							break;
						}
					}
					ans+=pos;
				}
			}
		}
	}
	return ans;
}

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