Submission #120980

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
120980	2019-06-25T20:57:42 Z	TadijaSebez	Pyramid Base (IOI08_pyramid_base)	C++11	Compilation error	0 ms	0 KB

pyramid_base

#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;
}
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]);
	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: At global scope:
pyramid_base.cpp:25:21: error: 'int y1 [400050]' redeclared as different kind of symbol
 int x1[P],x2[P],y1[P],y2[P],cost[P],p,n,m,B;
                     ^
In file included from /usr/include/features.h:367:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/os_defines.h:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/c++config.h:533,
                 from /usr/include/c++/7/cassert:43,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from pyramid_base.cpp:1:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:251:1: note: previous declaration 'double y1(double)'
 __MATHCALL (y1,, (_Mdouble_));
 ^
pyramid_base.cpp: In function 'bool Check(int)':
pyramid_base.cpp:32:31: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   evs.pb(Event(x1[i]-sz+1,y1[i]-sz+1,y2[i],cost[i]));
                               ^
pyramid_base.cpp:32:32: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   evs.pb(Event(x1[i]-sz+1,y1[i]-sz+1,y2[i],cost[i]));
                           ~~~~~^~~
pyramid_base.cpp:32:35: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   evs.pb(Event(x1[i]-sz+1,y1[i]-sz+1,y2[i],cost[i]));
                           ~~~~~~~~^~
pyramid_base.cpp:32:35: error: invalid conversion from 'double (*)(double) throw ()' to 'int' [-fpermissive]
pyramid_base.cpp:22:2: note:   initializing argument 2 of 'Event::Event(int, int, int, int)'
  Event(int a, int b, int c, int d):tme(a),l(b),r(c),f(d){}
  ^~~~~
pyramid_base.cpp:33:28: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   evs.pb(Event(x2[i]+1,y1[i]-sz+1,y2[i],-cost[i]));
                            ^
pyramid_base.cpp:33:29: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   evs.pb(Event(x2[i]+1,y1[i]-sz+1,y2[i],-cost[i]));
                        ~~~~~^~~
pyramid_base.cpp:33:32: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   evs.pb(Event(x2[i]+1,y1[i]-sz+1,y2[i],-cost[i]));
                        ~~~~~~~~^~
pyramid_base.cpp:33:32: error: invalid conversion from 'double (*)(double) throw ()' to 'int' [-fpermissive]
pyramid_base.cpp:22:2: note:   initializing argument 2 of 'Event::Event(int, int, int, int)'
  Event(int a, int b, int c, int d):tme(a),l(b),r(c),f(d){}
  ^~~~~
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 function 'int main()':
pyramid_base.cpp:50:59: warning: pointer to a function used in arithmetic [-Wpointer-arith]
  for(int i=1;i<=p;i++) scanf("%i %i %i %i %i",&x1[i],&y1[i],&x2[i],&y2[i],&cost[i]);
                                                           ^
pyramid_base.cpp:50:83: warning: format '%i' expects argument of type 'int*', but argument 3 has type 'double (*)(double) throw ()' [-Wformat=]
  for(int i=1;i<=p;i++) scanf("%i %i %i %i %i",&x1[i],&y1[i],&x2[i],&y2[i],&cost[i]);
                                                      ~~~~~~                       ^
pyramid_base.cpp:54:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=top+bot>>1;
       ~~~^~~~
pyramid_base.cpp:49: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:50: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]);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~