oj.uz

Submission #410479

# Submission time Handle Problem Language Result Execution time Memory
410479 2021-05-22T18:26:27 Z Jasiekstrz Pyramid Base (IOI08_pyramid_base) C++17
45 / 100
 5000 ms 30660 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N0=4e5;
const int P0=11e5;
struct Rec
{
	int x1,x2,y1,y2;
	int c;
};
Rec tab[N0+10];
int pot0;
int tree0[2*P0+10];
int upd0[2*P0+10];
bool comp0(Rec &a,Rec &b)
{
	return a.x1<b.x1;
}
void pushdown0(int i)
{
	for(int it:{2*i,2*i+1})
	{
		tree0[it]=max(tree0[it],upd0[i]);
		upd0[it]=max(upd0[it],upd0[i]);
	}
	upd0[i]=0;
	return;
}
void add0(int i,int l,int r,int ls,int rs,int c)
{
	if(r<ls || rs<l)
		return;
	else if(ls<=l && r<=rs)
	{
		tree0[i]=max(tree0[i],c);
		upd0[i]=max(upd0[i],c);
		return;
	}
	pushdown0(i);
	int mid=(l+r)/2;
	add0(2*i,l,mid,ls,rs,c);
	add0(2*i+1,mid+1,r,ls,rs,c);
	tree0[i]=min(tree0[2*i],tree0[2*i+1]);
	return;
}
bool check0(int m,int n,int p,int d)
{
	for(int i=1;i<=n-d+1;i++)
		tree0[pot0+i-1]=1;
	for(int i=n-d+2;i<=pot0;i++)
		tree0[pot0+i-1]=m+1;
	for(int i=pot0-1;i>=1;i--)
		tree0[i]=min(tree0[2*i],tree0[2*i+1]);
	for(int i=1;i<2*pot0;i++)
		upd0[i]=0;
	for(int i=1,it=1;i<=m;i++)
	{
		while(it<=p && tab[it].x1<=i)
		{
			//cerr<<i<<": "<<tab[it].x1<<" "<<tab[it].x2<<" "<<tab[it].y1<<" "<<tab[it].y2<<"\n";
			add0(1,1,pot0,max(1,tab[it].y1-d+1),tab[it].y2,tab[it].x2+1);
			it++;
		}
		if(i-tree0[1]+1>=d)
		{
			//cerr<<i<<" "<<tree0[1]<<"\n";
			return true;
		}
	}
	return false;
}
int solve0(int m,int n,int p)
{
	sort(tab+1,tab+p+1,comp0);
	for(pot0=1;pot0<=n;pot0*=2);
	//cerr<<check0(m,n,p,6)<<"\n";
	//return 0;
	int bg=0,en=min(n,m);
	while(bg<en)
	{
		int mid=(bg+en+1)/2;
		if(check0(m,n,p,mid))
			bg=mid;
		else
			en=mid-1;
	}
	return bg;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int m,n,b,p;
	cin>>m>>n>>b>>p;
	for(int i=1;i<=p;i++)
		cin>>tab[i].x1>>tab[i].y1>>tab[i].x2>>tab[i].y2>>tab[i].c;
	cout<<solve0(m,n,p)<<"\n";
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 588 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2380 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 16744 KB Output is correct
2 Correct 121 ms 16796 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 16740 KB Output is correct
2 Correct 116 ms 16776 KB Output is correct

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 145 ms 2656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 493 ms 17116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 512 ms 17212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 657 ms 17304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3251 ms 21572 KB Output is correct
2 Correct 475 ms 11460 KB Output is correct

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4897 ms 24116 KB Output is correct
2 Execution timed out 5062 ms 30660 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5061 ms 26736 KB Time limit exceeded
2 Halted 0 ms 0 KB -