oj.uz

Submission #891476

# Submission time Handle Problem Language Result Execution time Memory
891476 2023-12-23T05:28:11 Z Muhammad_Aneeq Rectangles (IOI19_rect) C++17
25 / 100
 5000 ms 136400 KB 
#include <vector>
#include <iostream>
using namespace std;
int const N=2600;
bool z1=0;
struct segt
{
	vector<int>a;
	int seg[4*N];
	segt(vector<int>&s)
	{
		a=s;
		build(1,0,a.size()-1);
	}	
	void build(int i,int st,int en)
	{
		if (st==en)
		{
			seg[i]=a[st];
			return;
		}
		int mid=(st+en)/2;
		build(i*2,st,mid);build(i*2+1,mid+1,en);
		seg[i]=max(seg[i*2],seg[i*2+1]);
	}
	int get(int i,int l,int r,int st,int en)
	{
		if (st>=l&&en<=r)
			return seg[i];
		if (st>r||en<l)
			return 0;
		int mid=(st+en)/2;
		return max(get(i*2,l,r,st,mid),get(i*2+1,l,r,mid+1,en));
	}
};
segt* St[2][N]={NULL};
long long count_rectangles(vector<vector<int>>a)
{
	int n=a.size(),m=a[0].size();
	for (int i=0;i<n;i++)
		St[0][i]=new segt(a[i]);
	for (int i=0;i<m;i++)
	{
		vector<int>z;
		for (int j=0;j<n;j++)
			z.push_back(a[j][i]);
		z1=(i==3);
		St[1][i]=new segt(z);
	}
	long long ans=0;
	for (int i=1;i<n-1;i++)
	{
		for (int j=1;j<m-1;j++)
		{
			for (int k=i;k<n-1;k++)
			{
				for (int l=j;l<m-1;l++)
				{
					bool w=0;
					bool z=0;
					if (i==4&&j==3&&k==4&&l==3)
					{
						z=1;
					}
					for (int o=i;o<=k&&!w;o++)
					{
						int f=St[0][o]->get(1,j,l,0,m-1);
						if (f>=a[o][j-1]||f>=a[o][l+1])
							w=1;
					}
					for (int o=j;o<=l&&!w;o++)
					{
						int f=St[1][o]->get(1,i,k,0,n-1); 
						if (f>=a[i-1][o]||f>=a[k+1][o])
							w=1;
					}
					ans+=(!w);
				}
			}
		}
	}
	return ans;
}

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:60:11: warning: variable 'z' set but not used [-Wunused-but-set-variable]
   60 |      bool z=0;
      |           ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 7 ms 604 KB Output is correct
3 Correct 7 ms 708 KB Output is correct
4 Correct 7 ms 856 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 1 ms 628 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 5 ms 604 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 5 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 5 ms 708 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 7 ms 604 KB Output is correct
3 Correct 7 ms 708 KB Output is correct
4 Correct 7 ms 856 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 1 ms 628 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 5 ms 604 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 5 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 5 ms 708 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 538 ms 1372 KB Output is correct
23 Correct 536 ms 1348 KB Output is correct
24 Correct 551 ms 1372 KB Output is correct
25 Correct 357 ms 1372 KB Output is correct
26 Correct 354 ms 1360 KB Output is correct
27 Correct 349 ms 1116 KB Output is correct
28 Correct 376 ms 1368 KB Output is correct
29 Correct 77 ms 1112 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 7 ms 604 KB Output is correct
3 Correct 7 ms 708 KB Output is correct
4 Correct 7 ms 856 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 1 ms 628 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 5 ms 604 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 5 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 538 ms 1372 KB Output is correct
18 Correct 536 ms 1348 KB Output is correct
19 Correct 551 ms 1372 KB Output is correct
20 Correct 357 ms 1372 KB Output is correct
21 Correct 354 ms 1360 KB Output is correct
22 Correct 349 ms 1116 KB Output is correct
23 Correct 376 ms 1368 KB Output is correct
24 Correct 77 ms 1112 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 5 ms 708 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Execution timed out 5016 ms 3416 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 7 ms 604 KB Output is correct
3 Correct 7 ms 708 KB Output is correct
4 Correct 7 ms 856 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 1 ms 628 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 5 ms 604 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 5 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 538 ms 1372 KB Output is correct
18 Correct 536 ms 1348 KB Output is correct
19 Correct 551 ms 1372 KB Output is correct
20 Correct 357 ms 1372 KB Output is correct
21 Correct 354 ms 1360 KB Output is correct
22 Correct 349 ms 1116 KB Output is correct
23 Correct 376 ms 1368 KB Output is correct
24 Correct 77 ms 1112 KB Output is correct
25 Execution timed out 5016 ms 3416 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 11088 KB Output is correct
2 Correct 224 ms 9304 KB Output is correct
3 Correct 293 ms 11088 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 290 ms 10896 KB Output is correct
6 Correct 289 ms 10840 KB Output is correct
7 Correct 288 ms 10984 KB Output is correct
8 Correct 290 ms 10840 KB Output is correct
9 Correct 292 ms 10984 KB Output is correct
10 Correct 5 ms 11096 KB Output is correct
11 Correct 5 ms 10844 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 5 ms 708 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Execution timed out 5062 ms 136400 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 7 ms 604 KB Output is correct
3 Correct 7 ms 708 KB Output is correct
4 Correct 7 ms 856 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Correct 5 ms 604 KB Output is correct
7 Correct 1 ms 628 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 5 ms 604 KB Output is correct
10 Correct 5 ms 604 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 5 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 538 ms 1372 KB Output is correct
18 Correct 536 ms 1348 KB Output is correct
19 Correct 551 ms 1372 KB Output is correct
20 Correct 357 ms 1372 KB Output is correct
21 Correct 354 ms 1360 KB Output is correct
22 Correct 349 ms 1116 KB Output is correct
23 Correct 376 ms 1368 KB Output is correct
24 Correct 77 ms 1112 KB Output is correct
25 Execution timed out 5016 ms 3416 KB Time limit exceeded
26 Halted 0 ms 0 KB -