oj.uz

Submission #410812

# Submission time Handle Problem Language Result Execution time Memory
410812 2021-05-23T18:59:12 Z Jasiekstrz Pyramid Base (IOI08_pyramid_base) C++17
100 / 100
 1358 ms 69660 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=4e5;
const int P=11e5;
struct Rec
{
	int x1,x2,y1,y2;
	int val;
};
bool comp(Rec &a,Rec &b)
{
	return a.x1<b.x1;
}
Rec tab[N+10];
int pot;
int tree[2*P+10];
int upd[2*P+10];
int pref[2*P+10];
int suf[2*P+10];
bool all[2*P+10];
int clr[2*P+10];
Rec ev1[2*N+10];
void merge(int i)
{
	if(clr[2*i] && clr[2*i+1])
	{
		tree[i]=pref[i]=suf[i]=0;
		all[i]=false;
	}
	else if(clr[2*i])
	{
		tree[i]=tree[2*i+1];
		suf[i]=suf[2*i+1];
		pref[i]=0;
		all[i]=false;
	}
	else if(clr[2*i+1])
	{
		tree[i]=tree[2*i];
		suf[i]=0;
		pref[i]=pref[2*i];
		all[i]=false;
	}
	else
	{
		all[i]=(all[2*i] && all[2*i+1]);
		pref[i]=(all[2*i] ? pref[2*i]+pref[2*i+1]:pref[2*i]);
		suf[i]=(all[2*i+1] ? suf[2*i]+suf[2*i+1]:suf[2*i+1]);
		tree[i]=max({tree[2*i],tree[2*i+1],suf[2*i]+pref[2*i+1]});
	}
	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)
	{
		clr[i]+=c;
		return;
	}
	int mid=(l+r)/2;
	add0(2*i,l,mid,ls,rs,c);
	add0(2*i+1,mid+1,r,ls,rs,c);
	merge(i);
	return;
}
int solve0(int m,int n,int p)
{
	for(int i=1;i<=p;i++)
	{
		ev1[2*i-1]=ev1[2*i]=tab[i];
		ev1[2*i-1].x2=0;
		ev1[2*i].x1=ev1[2*i].x2; ev1[2*i].x2=1;
	}
	sort(ev1+1,ev1+2*p+1,comp);
	for(pot=1;pot<=n;pot*=2);
	for(int i=pot;i<=pot+n-1;i++)
	{
		tree[i]=pref[i]=suf[i]=1;
		all[i]=true;
		clr[i]=0;
	}
	for(int i=pot+n;i<2*pot;i++)
	{
		tree[i]=pref[i]=suf[i]=0;
		all[i]=false;
		clr[i]=0;
	}
	for(int i=pot-1;i>=1;i--)
		merge(i);
	int ans=0;
	for(int i=1,j=0,l=1,r=1;i<=m;i++)
	{
		while(l<=2*p && ev1[l].x1<i)
		{
			if(ev1[l].x2==1)
				add0(1,1,pot,ev1[l].y1,ev1[l].y2,-1);
			l++;
		}
		while(j<=m && tree[1]>=j-i+1 && clr[1]==0)
		{
			j++;
			while(r<=2*p && ev1[r].x1<=j)
			{
				if(ev1[r].x2==0)
					add0(1,1,pot,ev1[r].y1,ev1[r].y2,1);
				r++;
			}
		}
		ans=max(ans,j-i);
	}
	return ans;
}
void pushdown1(int i)
{
	for(int it:{2*i,2*i+1})
	{
		tree[it]+=upd[i];
		upd[it]+=upd[i];
	}
	upd[i]=0;
	return;
}
void add1(int i,int l,int r,int ls,int rs,int c)
{
	if(r<ls || rs<l)
		return;
	else if(ls<=l && r<=rs)
	{
		tree[i]+=c;
		upd[i]+=c;
		return;
	}
	pushdown1(i);
	int mid=(l+r)/2;
	add1(2*i,l,mid,ls,rs,c);
	add1(2*i+1,mid+1,r,ls,rs,c);
	tree[i]=min(tree[2*i],tree[2*i+1]);
	return;
}
bool check1(int m,int n,int b,int p,int d)
{
	for(int i=1;i<=p;i++)
	{
		ev1[2*i-1]=ev1[2*i]=tab[i];
		ev1[2*i-1].x2=0;
		ev1[2*i].x1=ev1[2*i].x2+d; ev1[2*i].x2=1;
	}
	sort(ev1+1,ev1+2*p+1,comp);
	for(int i=1;i<=n-d+1;i++)
		tree[pot+i-1]=0;
	for(int i=n-d+2;i<=pot;i++)
		tree[pot+i-1]=b+1;
	for(int i=pot-1;i>=1;i--)
		tree[i]=min(tree[2*i],tree[2*i+1]);
	for(int i=1;i<2*pot;i++)
		upd[i]=0;
	for(int i=1,it=1;i<=m;i++)
	{
		while(it<=2*p && ev1[it].x1<=i)
		{
			if(ev1[it].x2==0)
				add1(1,1,pot,max(1,ev1[it].y1-d+1),ev1[it].y2,ev1[it].val);
			else
				add1(1,1,pot,max(1,ev1[it].y1-d+1),ev1[it].y2,-ev1[it].val);
			it++;
		}
		if(d<=i && tree[1]<=b)
		{
			//cerr<<i<<" "<<tree[1]<<"\n";
			return true;
		}
	}
	return false;
}
int solve1(int m,int n,int b,int p)
{
	for(pot=1;pot<=n;pot*=2);
	int bg=0,en=min(n,m);
	while(bg<en)
	{
		int mid=(bg+en+1)/2;
		if(check1(m,n,b,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].val;
	if(b==0)
		cout<<solve0(m,n,p)<<"\n";
	else
		cout<<solve1(m,n,b,p)<<"\n";
	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 34212 KB Output is correct
2 Correct 32 ms 34620 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31112 KB Output is correct
2 Correct 31 ms 34228 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 972 KB Output is correct
2 Correct 69 ms 972 KB Output is correct
3 Correct 57 ms 980 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 3620 KB Output is correct
2 Correct 373 ms 3672 KB Output is correct
3 Correct 311 ms 3636 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 18488 KB Output is correct
2 Correct 55 ms 1920 KB Output is correct
3 Correct 203 ms 18248 KB Output is correct
4 Correct 613 ms 18540 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 756 ms 18920 KB Output is correct
2 Correct 1008 ms 18928 KB Output is correct
3 Correct 548 ms 18884 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 800 ms 19368 KB Output is correct
2 Correct 1282 ms 19396 KB Output is correct
3 Correct 1244 ms 19356 KB Output is correct
4 Correct 1325 ms 19360 KB Output is correct
5 Correct 1358 ms 19340 KB Output is correct
6 Correct 619 ms 19452 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 48756 KB Output is correct
2 Correct 260 ms 18244 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 723 ms 54192 KB Output is correct
2 Correct 744 ms 54740 KB Output is correct
3 Correct 496 ms 60364 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 885 ms 56620 KB Output is correct
2 Correct 1110 ms 69660 KB Output is correct
3 Correct 1100 ms 69464 KB Output is correct
4 Correct 963 ms 69292 KB Output is correct
5 Correct 661 ms 69648 KB Output is correct