oj.uz

Submission #119094

# Submission time Handle Problem Language Result Execution time Memory
119094 2019-06-20T10:18:31 Z baluteshih Pyramid Base (IOI08_pyramid_base) C++14
35 / 100
 5000 ms 49000 KB 
#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

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.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 33296 KB Output is correct
2 Correct 360 ms 33296 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 33404 KB Output is correct
2 Correct 355 ms 33308 KB Output is correct

Subtask #8
0 / 7.0

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

Subtask #9
0 / 7.0

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

Subtask #10
0 / 7.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 10.0

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

Subtask #14
0 / 10.0

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

Subtask #15
0 / 10.0

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