oj.uz

Submission #120990

# Submission time Handle Problem Language Result Execution time Memory
120990 2019-06-25T21:46:16 Z TadijaSebez Pyramid Base (IOI08_pyramid_base) C++11
100 / 100
 2475 ms 136936 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=1000050;
const int M=2*N;
const int P=400050;
int root,tsz,mn[M],lzy[M],ls[M],rs[M];
void Set(int &c, int ss, int se, int qs, int qe, int f)
{
	if(qs>qe || qs>se || ss>qe) return;
	if(!c) c=++tsz;
	if(qs<=ss && qe>=se){ lzy[c]+=f;mn[c]+=f;return;}
	int mid=ss+se>>1;
	Set(ls[c],ss,mid,qs,qe,f);
	Set(rs[c],mid+1,se,qs,qe,f);
	mn[c]=min(mn[ls[c]],mn[rs[c]])+lzy[c];
}
void Clear(){ for(int i=1;i<=tsz;i++) ls[i]=rs[i]=mn[i]=lzy[i]=0;tsz=root=0;}
struct Event
{
	int tme,l,r,f;
	Event(int a, int b, int c, int d):tme(a),l(b),r(c),f(d){}
	bool operator < (Event b) const { return tme<b.tme;}
};
int X1[P],X2[P],Y1[P],Y2[P],cost[P],p,n,m,B;
bool Check(int sz)
{
	Clear();
	vector<Event> evs;
	for(int i=1;i<=p;i++)
	{
		evs.pb(Event(X1[i]-sz+1,Y1[i]-sz+1,Y2[i],cost[i]));
		evs.pb(Event(X2[i]+1,Y1[i]-sz+1,Y2[i],-cost[i]));
	}
	sort(evs.begin(),evs.end());
	int lst=0;
	for(int i=0;i<evs.size();i++)
	{
		int t=evs[i].tme-lst;
		lst=evs[i].tme;
		if(t>0 && lst>1 && mn[root]<=B) return 1;
		Set(root,1,m-sz+1,evs[i].l,evs[i].r,evs[i].f);
		if(lst>n-sz+1) break;
	}
	return 0;
}
struct Node
{
	int sum,l,r,mx,sz;
	Node(){}
	Node(int a, int b, int c, int d, int e):sum(a),l(b),r(c),mx(d),sz(e){}
	int Get(){ return sum?0:mx;}
	void Check(){ if(sum) l=r=mx=0;}
};
void Merge(Node &c, Node ls, Node rs)
{
	ls.Check();
	rs.Check();
	c=Node(c.sum,ls.l+(ls.l==ls.sz?rs.l:0),rs.r+(rs.r==rs.sz?ls.r:0),max(max(ls.mx,rs.mx),ls.r+rs.l),ls.sz+rs.sz);
}
struct STIntervals
{
	int ls[M],rs[M],tsz,root;
	Node node[M];
	STIntervals(){}
	void Build(int &c, int ss, int se)
	{
		c=++tsz;
		if(ss==se){ node[c]=Node(0,1,1,1,1);return;}
		int mid=ss+se>>1;
		Build(ls[c],ss,mid);
		Build(rs[c],mid+1,se);
		Merge(node[c],node[ls[c]],node[rs[c]]);
	}
	void Set(int &c, int ss, int se, int qs, int qe, int f)
	{
		if(qs>qe || qs>se || ss>qe) return;
		if(qs<=ss && qe>=se){ node[c].sum+=f;return;}
		int mid=ss+se>>1;
		Set(ls[c],ss,mid,qs,qe,f);
		Set(rs[c],mid+1,se,qs,qe,f);
		Merge(node[c],node[ls[c]],node[rs[c]]);
	}
	int Get(){ return node[root].Get();}
} ST;
vector<int> add[N],del[N];
void Solve()
{
	for(int i=1;i<=p;i++)
	{
		add[X1[i]].pb(i);
		del[X2[i]+1].pb(i);
	}
	ST.Build(ST.root,1,m);
	int ans=0;
	for(int i=1,j=1;i<=n;i++)
	{
		for(int k:del[i]) ST.Set(ST.root,1,m,Y1[k],Y2[k],-1);
		while(j<=n+1 && ST.Get()>=j-i)
		{
			ans=max(ans,j-i);
			for(int k:add[j]) ST.Set(ST.root,1,m,Y1[k],Y2[k],1);
			j++;
		}
	}
	printf("%i\n",ans);
}
int main()
{
	scanf("%i %i %i %i",&n,&m,&B,&p);
	for(int i=1;i<=p;i++) scanf("%i %i %i %i %i",&X1[i],&Y1[i],&X2[i],&Y2[i],&cost[i]);
	if(B==0){ Solve();return 0;}
	int top=min(n,m),bot=1,mid,ans=0;
	while(top>=bot)
	{
		mid=top+bot>>1;
		if(Check(mid)) ans=mid,bot=mid+1;
		else top=mid-1;
	}
	printf("%i\n",ans);
	return 0;
}

Compilation message

pyramid_base.cpp: In function 'void Set(int&, int, int, int, int, int)':
pyramid_base.cpp:13:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
pyramid_base.cpp: In function 'bool Check(int)':
pyramid_base.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<evs.size();i++)
              ~^~~~~~~~~~~
pyramid_base.cpp: In member function 'void STIntervals::Build(int&, int, int)':
pyramid_base.cpp:70:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=ss+se>>1;
           ~~^~~
pyramid_base.cpp: In member function 'void STIntervals::Set(int&, int, int, int, int, int)':
pyramid_base.cpp:79:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=ss+se>>1;
           ~~^~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:116:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=top+bot>>1;
       ~~~^~~~
pyramid_base.cpp:110:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i %i",&n,&m,&B,&p);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp:111:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=p;i++) scanf("%i %i %i %i %i",&X1[i],&Y1[i],&X2[i],&Y2[i],&cost[i]);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 102240 KB Output is correct
2 Correct 110 ms 102136 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 102236 KB Output is correct
2 Correct 108 ms 102136 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 47988 KB Output is correct
2 Correct 98 ms 48116 KB Output is correct
3 Correct 79 ms 48108 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 49520 KB Output is correct
2 Correct 351 ms 50044 KB Output is correct
3 Correct 270 ms 49864 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 51124 KB Output is correct
2 Correct 77 ms 49460 KB Output is correct
3 Correct 180 ms 53112 KB Output is correct
4 Correct 393 ms 52796 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 52068 KB Output is correct
2 Correct 680 ms 53648 KB Output is correct
3 Correct 184 ms 50912 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 51780 KB Output is correct
2 Correct 932 ms 54780 KB Output is correct
3 Correct 878 ms 54852 KB Output is correct
4 Correct 932 ms 54752 KB Output is correct
5 Correct 990 ms 54844 KB Output is correct
6 Correct 177 ms 51336 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1287 ms 117484 KB Output is correct
2 Correct 421 ms 62968 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1825 ms 124392 KB Output is correct
2 Correct 1558 ms 120404 KB Output is correct
3 Correct 863 ms 112208 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1748 ms 130732 KB Output is correct
2 Correct 2377 ms 128100 KB Output is correct
3 Correct 2475 ms 128112 KB Output is correct
4 Correct 2211 ms 136936 KB Output is correct
5 Correct 1146 ms 131168 KB Output is correct