Submission #119094

#	Time	Username	Problem	Language	Result	Execution time	Memory
119094		baluteshih	Pyramid Base (IOI08_pyramid_base)	C++14	35 / 100	5097 ms	49000 KiB

pyramid_base

#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int seg[3][4000005],lazy[4000005],p,n,m;
vector<int> v;

void reset(int l,int r,int rt)
{
	lazy[rt]=0;
	if(l==r)
		return seg[0][rt]=seg[1][rt]=seg[2][rt]=1,void();
	int m=l+r>>1;
	reset(l,m,rt<<1),reset(m+1,r,rt<<1|1);
	seg[0][rt]=seg[1][rt]=seg[2][rt]=r-l+1;
}

void modify(int L,int R,int l,int r,int rt,int v)
{
	if(L<=l&&R>=r)
		return lazy[rt]+=v,void();
	int m=l+r>>1;
	if(L<=m) modify(L,R,l,m,rt<<1,v);
	if(R>m) modify(L,R,m+1,r,rt<<1|1,v);
	if(lazy[rt<<1]&&lazy[rt<<1|1])
		seg[0][rt]=seg[1][rt]=seg[2][rt]=0;
	else if(lazy[rt<<1|1])
	{
		seg[2][rt]=seg[2][rt<<1];
		seg[0][rt]=seg[0][rt<<1];
		seg[1][rt]=0;
	}
	else if(lazy[rt<<1])
	{
		seg[2][rt]=seg[2][rt<<1|1];
		seg[0][rt]=0;
		seg[1][rt]=seg[1][rt<<1|1];	
	}
	else
	{
		seg[2][rt]=max({seg[2][rt<<1],seg[2][rt<<1|1],seg[1][rt<<1]+seg[0][rt<<1|1]});
		if(seg[0][rt<<1]==m-l+1)
			seg[0][rt]=seg[0][rt<<1]+seg[0][rt<<1|1];
		else	
			seg[0][rt]=seg[0][rt<<1];
		if(seg[1][rt<<1|1]==r-m)
			seg[1][rt]=seg[1][rt<<1]+seg[1][rt<<1|1];
		else
			seg[1][rt]=seg[1][rt<<1|1];
	}
}

struct add
{
	int x,l,r,cost;
	bool operator<(const add &a)const{
		return x<a.x;
	}
}arr[400005];

struct rmove
{
	int x,l,r,cost;
	bool operator<(const rmove &a)const{
		return x<a.x;
	}
}arr2[400005];

void mdfy(int l,int r,int v)
{
	//cout << "[" << l << ',' << r << "] += " << v << "\n";
	modify(l,r,1,m,1,v);
}
 
bool check(vector<int> &v,int sz)
{
	int nw=0,nw2=0;
	vector<int> tmp;
	for(int i:v)
	{
		while(nw<=p&&arr[nw].x<=i+sz)
			mdfy(arr[nw].l,arr[nw].r,1),++nw;
		while(nw2<p&&arr2[nw2].x<=i)
			mdfy(arr2[nw2].l,arr2[nw2].r,-1),++nw2;
		if(!lazy[1]&&seg[2][1]>=sz) tmp.pb(i);
	}
	if(tmp.size()) 
		return v.swap(tmp),1;
	return 0;
}
 
int main()
{jizz
	int b,l,r,x1,y1,x2,y2,c;
	cin >> n >> m >> b >> p,l=0,r=min(n,m),v.pb(0);
	for(int i=0;i<p;++i)
	{
		cin >> x1 >> y1 >> x2 >> y2 >> c;
		arr[i]=add{x1,y1,y2,c},arr2[i]=rmove{x2,y1,y2,c};
		v.pb(x2);
	}
	sort(arr,arr+p),arr[p]=add{n+1,1,m,0},sort(arr2,arr2+p);
	sort(ALL(v)),v.resize(unique(ALL(v))-v.begin());
	while(l<r)
	{
		int mid=(l+r)/2+1;
		reset(1,m,1);
		if(check(v,mid)) l=mid;
		else r=mid-1;
	}
	cout << l << "\n";
}

Compilation message (stderr)

pyramid_base.cpp: In function 'void reset(int, int, int)':
pyramid_base.cpp:24:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
pyramid_base.cpp: In function 'void modify(int, int, int, int, int, int)':
pyramid_base.cpp:33:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 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