Submission #263080

#	Time	Username	Problem	Language	Result	Execution time	Memory
263080		amiratou	Pyramid Base (IOI08_pyramid_base)	C++14	5 / 100	5098 ms	19704 KiB

pyramid_base

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define rando mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ld long double
#define ll long long
//#define int ll
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<int> >
#define mp make_pair
#define INF 1000000000
#define pb push_back
#define EPS 1e-9
const int MOD = 1000000007; // 998244353
struct obs
{
	int x1,y1,x2,y2,cost;
};
obs tab[400001];
int n,m,B,p;
bool inter(int idx,int X1,int Y1,int X2,int Y2){
	if(X1<=0 || Y1<=0 || X2>n || Y2>m)return 1;
	for (int i = 0; i < p; ++i)
	{
		if(i==idx)continue;
		if(Y1>=tab[i].y2 || Y2<=tab[i].y1)
			continue;
		if(X1>=tab[i].x2 || X2<=tab[i].x1)
			continue;
		return 1;
	}
	return 0;
}
int32_t main(){
	boost;
	//freopen(".in","r",stdin);
	cin>>n>>m>>B>>p;
	for (int i = 0; i < p; ++i)
		cin>>tab[i].x1>>tab[i].y1>>tab[i].x2>>tab[i].y2>>tab[i].cost;
	int l=0,r=min(n,m),ans=-1;
	while(l<=r){
		int med=(l+r)>>1;
		bool f=0;
		for (int i = 0; i < p; ++i)
		{
			int a,b,c,d;
			a=tab[i].x1;
			b=tab[i].y1-med;
			c=a+med-1,d=b+med-1;
			if(!inter(i,a,b,c,d)){f=1;break;}
			c=tab[i].x2;
			d=tab[i].y1;
			a=c-med+1,b=d-med+1;
			if(!inter(i,a,b,c,d)){f=1;break;}

			a=tab[i].x1+med;
			b=tab[i].y1;
			c=a+med-1,d=b+med-1;
			if(!inter(i,a,b,c,d)){f=1;break;}
			c=tab[i].x2+med;
			d=tab[i].y2;
			a=c-med+1,b=d-med+1;
			if(!inter(i,a,b,c,d)){f=1;break;}

			a=tab[i].x1;
			b=tab[i].y1+med;
			c=a+med-1,d=b+med-1;
			if(!inter(i,a,b,c,d)){f=1;break;}
			c=tab[i].x2;
			d=tab[i].y2+med;
			a=c-med+1,b=d-med+1;
			if(!inter(i,a,b,c,d)){f=1;break;}

			c=tab[i].x1;
			d=tab[i].y2;
			a=c-med+1,b=d-med+1;
			if(!inter(i,a,b,c,d)){f=1;break;}
			c=tab[i].x1;
			d=tab[i].y1+med;
			a=c-med+1,b=d-med+1;
			if(!inter(i,a,b,c,d)){f=1;break;}
		}
		if(f)l=med+1,ans=med;
		else r=med-1;
	}
	assert(ans!=-1);
	cout<<ans<<"\n";
	return 0;
}

//do smth instead of nothing and stay organized
//long long
//array bounds
//special cases
//binary search

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10