Submission #891490

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
891490	2023-12-23T05:50:00 Z	Faisal_Saqib	Rectangles (IOI19_rect)	C++17	0 / 100	5000 ms	1048576 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	15 ms	588 KB	Output is correct
3	Correct	12 ms	588 KB	Output is correct
4	Correct	12 ms	348 KB	Output is correct
5	Correct	10 ms	840 KB	Output is correct
6	Correct	10 ms	348 KB	Output is correct
7	Correct	2 ms	348 KB	Output is correct
8	Correct	2 ms	348 KB	Output is correct
9	Correct	10 ms	348 KB	Output is correct
10	Correct	11 ms	584 KB	Output is correct
11	Correct	11 ms	348 KB	Output is correct
12	Correct	11 ms	592 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Runtime error	709 ms	1048576 KB	Execution killed with signal 9
15	Halted	0 ms	0 KB	-

Subtask #2

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	15 ms	588 KB	Output is correct
3	Correct	12 ms	588 KB	Output is correct
4	Correct	12 ms	348 KB	Output is correct
5	Correct	10 ms	840 KB	Output is correct
6	Correct	10 ms	348 KB	Output is correct
7	Correct	2 ms	348 KB	Output is correct
8	Correct	2 ms	348 KB	Output is correct
9	Correct	10 ms	348 KB	Output is correct
10	Correct	11 ms	584 KB	Output is correct
11	Correct	11 ms	348 KB	Output is correct
12	Correct	11 ms	592 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Runtime error	709 ms	1048576 KB	Execution killed with signal 9
15	Halted	0 ms	0 KB	-

Subtask #3

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	15 ms	588 KB	Output is correct
3	Correct	12 ms	588 KB	Output is correct
4	Correct	12 ms	348 KB	Output is correct
5	Correct	10 ms	840 KB	Output is correct
6	Correct	10 ms	348 KB	Output is correct
7	Correct	2 ms	348 KB	Output is correct
8	Correct	2 ms	348 KB	Output is correct
9	Correct	10 ms	348 KB	Output is correct
10	Correct	11 ms	584 KB	Output is correct
11	Correct	11 ms	348 KB	Output is correct
12	Correct	11 ms	592 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Runtime error	709 ms	1048576 KB	Execution killed with signal 9
15	Halted	0 ms	0 KB	-

Subtask #4

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	15 ms	588 KB	Output is correct
3	Correct	12 ms	588 KB	Output is correct
4	Correct	12 ms	348 KB	Output is correct
5	Correct	10 ms	840 KB	Output is correct
6	Correct	10 ms	348 KB	Output is correct
7	Correct	2 ms	348 KB	Output is correct
8	Correct	2 ms	348 KB	Output is correct
9	Correct	10 ms	348 KB	Output is correct
10	Correct	11 ms	584 KB	Output is correct
11	Correct	11 ms	348 KB	Output is correct
12	Correct	11 ms	592 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Runtime error	709 ms	1048576 KB	Execution killed with signal 9
15	Halted	0 ms	0 KB	-

Subtask #5

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4399 ms	836 KB	Output is correct
2	Correct	2696 ms	772 KB	Output is correct
3	Correct	289 ms	860 KB	Output is correct
4	Runtime error	641 ms	1048576 KB	Execution killed with signal 9
5	Halted	0 ms	0 KB	-

Subtask #6

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Execution timed out	5113 ms	559260 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #7

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	15 ms	588 KB	Output is correct
3	Correct	12 ms	588 KB	Output is correct
4	Correct	12 ms	348 KB	Output is correct
5	Correct	10 ms	840 KB	Output is correct
6	Correct	10 ms	348 KB	Output is correct
7	Correct	2 ms	348 KB	Output is correct
8	Correct	2 ms	348 KB	Output is correct
9	Correct	10 ms	348 KB	Output is correct
10	Correct	11 ms	584 KB	Output is correct
11	Correct	11 ms	348 KB	Output is correct
12	Correct	11 ms	592 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Runtime error	709 ms	1048576 KB	Execution killed with signal 9
15	Halted	0 ms	0 KB	-