Submission #41775799

---

Source Code Expand

#include <bits/stdc++.h>
#define int __int128
#define pb push_back
using namespace std;
class fastIO{private:char ibuf[50007],*p1=ibuf,*p2=ibuf,obuf[50007],*p3=obuf,sta[50];bool file_end=false;char get(){return p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,50007,stdin),p1==p2)?(file_end=true),char(EOF):*p1++;}void put(const char x){p3-obuf<50007?*p3++=x:(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x);}public:explicit operator bool(){return!file_end;}size_t flush(){size_t f=fwrite(obuf,p3-obuf,1,stdout);p3=obuf;*p3=0;return f;}fastIO&operator>>(char&t){for(t=get();!isgraph(t);t=get());return*this;}template<typename any>typename std::enable_if<std::is_same<any,char>::value,any>::type tpval(){char t;for(t=get();!isgraph(t);t=get());return t;}fastIO&operator>>(char*t){char c;for(c=get();!isgraph(c);c=get());for(;isgraph(c);c=get())*t=c,t++;*t=0;return*this;}fastIO&operator>>(std::string&t){t.clear();char c;for(c=get();!isgraph(c);c=get());for(;isgraph(c);c=get())t+=c;return*this;}template<typename any>typename std::enable_if<std::is_same<any,std::string>::value,any>::type tpval(){std::string t;char c;for(c=get();!isgraph(c);c=get());for(;isgraph(c);c=get())t+=c;return t;}template<typename any>typename std::enable_if<(std::is_signed<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__int128_t>::value,fastIO>::type&operator>>(any&t){t=0;bool y=0;char c=get();for(;!isdigit(c);c=get())if(c==45)y=true;for(;isdigit(c);c=get())t=t*10+c-48;if(y==1)t=-t;return*this;}template<typename any>typename std::enable_if<(std::is_signed<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__int128_t>::value,any>::type tpval(){any t=0;bool y=0;char c=get();for(;!isdigit(c);c=get())if(c==45)y=true;for(;isdigit(c);c=get())t=t*10+c-48;if(y==1)t=-t;return t;}template<typename any>typename std::enable_if<(std::is_unsigned<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__uint128_t>::value,fastIO>::type&operator>>(any&t){t=0;char c=get();for(;!isdigit(c);c=get());for(;isdigit(c);c=get())t=t*10+c-48;return*this;}template<typename any>typename std::enable_if<(std::is_unsigned<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__uint128_t>::value,any>::type tpval(){any t=0;char c=get();for(;!isdigit(c);c=get());for(;isdigit(c);c=get())t=t*10+c-48;return t;}template<typename any1,typename any2>fastIO&operator>>(std::pair<any1,any2>&t){return*this>>t.first>>t.second;}template<typename any1,typename any2>std::pair<any1,any2>tpval(){return std::pair<any1,any2>(tpval<any1>(),tpval<any2>());}template<typename any>fastIO&read(any&t){return*this>>t;}fastIO&read(char*t){char c;for(c=get();!isgraph(c);c=get());for(;isgraph(c);c=get())*t=c,t++;*t=0;return*this;}template<typename any,typename...args>fastIO&read(any&t1,args&...t2){return(*this>>t1).read(t2...);}fastIO&operator<<(const char t){put(t);return*this;}fastIO&operator<<(const char*t){for(;*t;t++)put(*t);return*this;}fastIO&operator<<(const std::string&t){for(const char it:t)put(it);return*this;}template<typename any>typename std::enable_if<(std::is_signed<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__int128_t>::value,fastIO>::type&operator<<(any t){if(!t){put(48);return*this;}int len=0;if(t<0)t=-t,put(45);while(t)sta[len++]=char(t%10+48),t/=10;while(len--)put(sta[len]);return*this;}template<typename any>typename std::enable_if<(std::is_unsigned<any>::value&&std::is_integral<any>::value&&!std::is_same<any,char>::value)||std::is_same<any,__uint128_t>::value,fastIO>::type&operator<<(any t){if(!t){put(48);return*this;}int len=0;while(t)sta[len++]=char(t%10+48),t/=10;while(len--)put(sta[len]);return*this;}template<typename any1,typename any2>fastIO&operator<<(const std::pair<any1,any2>&t){return*this<<t.first<<' '<<t.second;}template<typename any>fastIO&write(const any&t){return*this<<t;}template<typename any,typename...args>fastIO&write(const any&t1,const args&...t2){return(*this<<t1).write(t2...);}~fastIO(){fwrite(obuf,p3-obuf,1,stdout);}}fio;
#define cin fio
#define cout fio
const int INF=1e6+5;
struct P3{
	int t,d,t1;
}aa[INF];
int n,h,Max[INF],Max1[INF];
int calc(int l,int r,int li) {
	if (l>r) return 0;
//	if (l+r>=li*2) return li+1;
	return (l+r)*(r-l+1)/2;
}
int check(int x) {
	int sum=0;
	int xx=(x-aa[n].t);
	xx=max((int)(0),xx);
	if (xx && Max[n]>h/xx) return 1;
	sum+=Max[n]*xx;
	x-=xx;
//	cout<<sum<<" qwej\n";
	if (sum>=h) return 1;
	for (int i=n;i;i--) {
		if (x<=aa[i-1].t) continue;
		int xx=(x-aa[i-1].t);
		xx=max((int)(0),xx);
//		cout<<calc(aa[i-1].t+1,x,h/Max1[i])<<" "<<Max1[i]<<" ok?12312313\n";
		if (calc(aa[i-1].t+1,x,h/Max1[i])>h/Max1[i]) return 1;
		if (xx && Max[i-1]>h/xx) return 1;
//		cout<<sum<<" ok?\n";
		sum+=max(calc(aa[i-1].t+1,x,h/Max1[i])*Max1[i],Max[i-1]*xx);
		x-=xx;
		if (sum>=h) return 1;
	}
	
	return sum>=h;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin>>n>>h;
	for (int i=1;i<=n;i++) cin>>aa[i].t>>aa[i].d,aa[i].t1=aa[i].t*aa[i].d;
	sort(aa+1,aa+1+n,[](P3 xx,P3 yy){return xx.t<yy.t;});
	for (int i=1;i<=n;i++) Max[i]=max(Max[i-1],aa[i].t1);
	for (int i=n;i;i--) Max1[i]=max(Max1[i+1],aa[i].d);
	int l=0,r=2e18,ans=-1;
	while (l<=r) {
		int Mid=(l+r)>>1;
		if (check(Mid)) r=(ans=Mid)-1;
		else l=Mid+1;
	}
	if (ans==-1) return 1;
	cout<<ans<<"\n";
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘__int128 calc(__int128, __int128, __int128)’:
./Main.cpp:13:26: warning: unused parameter ‘li’ [-Wunused-parameter]
   13 | int calc(int l,int r,int li) {
      |                          ^

Judge Result