제출 #402027

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
402027		keta_tsimakuridze	금 캐기 (IZhO14_divide)	C++14	100 / 100	839 ms	9208 KiB

divide

#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
using namespace std;
const int N=2e5+5,mod=1e9+7,Inf=1e16;
int t,x[N],tree[4*N],d[N],g[N],pref[N],p[N],n;
string s;
int getans(int u,int start,int end,int l,int r){
	if(l>end || r<start) return -Inf;
	if(start<=l && r<=end) return tree[u];
	int mid=(l+r)/2;
	return max(getans(2*u,start,end,l,mid),getans(2*u+1,start,end,mid+1,r));
}
void build(int u,int l,int r){
	if(l==r) {
		tree[u] = +x[l+1]-pref[l];
		return;
	}
	int mid=(l+r)/2;
	build(2*u,l,mid);
	build(2*u+1,mid+1,r);
	tree[u] = max(tree[2*u],tree[2*u+1]);
}
bool check(int g){
	int l = 0;
	for(int i=1;i<=n;i++){
		while(l<i && p[i]-p[l]>=g) l++;
		// x[r]-x[l]+b[r] - b[l-1]  >=
		if(l==1 && pref[i]-x[i]+x[1] >= 0) return 1;
		if(getans(1,1,l-1,1,n) - x[i] + pref[i]>=0) {
		 return 1;}
	}
	return 0;
}
 main(){
	// t=1;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>g[i]>>d[i];
	}
	int l=1,r=1e15,ans=0;
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i++){
		pref[i] = pref[i-1] + d[i];
		p[i] = p[i-1] + g[i];
	}
	build(1,1,n);
	while(l<=r){
		int mid=(l+r)/2,L=0;
		if(check(mid)){
			ans=mid;
			l=mid+1;
		}
		else r=mid-1;
	}
	cout<<ans;
}

컴파일 시 표준 에러 (stderr) 메시지

divide.cpp:36:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 |  main(){
      |  ^~~~
divide.cpp: In function 'int main()':
divide.cpp:50:19: warning: unused variable 'L' [-Wunused-variable]
   50 |   int mid=(l+r)/2,L=0;
      |                   ^

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52