제출 #173607

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
173607		nafis_shifat	Divide and conquer (IZhO14_divide)	C++14	100 / 100	281 ms	8824 KiB

divide

#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int mxn=1e5;
ll tree[4*mxn]={};
ll lazy[4*mxn]={};
int query(int node,int b,int e,int l,int r)
{
	if(b>r || e<l)return -1;
	if(b==e)return b;
	int mid=b+e>>1;
	int left=node<<1;
	int right=left|1;

	lazy[left]+=lazy[node];
    lazy[right]+=lazy[node];
    tree[left]+=lazy[node];
    tree[right]+=lazy[node];
    lazy[node]=0;



	if(tree[right]>=0)return query(right,mid+1,e,l,r);
	return query(left,b,mid,l,r);


    
}
void update(int node, int b,int e,int l,int r,ll v)
{
	if(b>r || e<l)return;


	if(b==e)
	{
		tree[node]+=v;
		return;
	}

	if(b>=l && e<=r)
	{
		tree[node]+=v;
		lazy[node]+=v;
		return;
	}
    int left=node*2;
    int right=node*2+1;

    lazy[left]+=lazy[node];
    lazy[right]+=lazy[node];
    tree[left]+=lazy[node];
    tree[right]+=lazy[node];
    lazy[node]=0;

    


    int mid=b+e>>1;
    update(left,b,mid,l,r,v);
    update(right,mid+1,e,l,r,v);

    tree[node]=max(tree[left],tree[right]);
}


int main()
{

	int n;
	cin>>n;
	ll g[n+1]={};
	ll d[n+1]={};
	int x[n+1]={};
	ll ans=-1;
	for(int i=1;i<=n;i++)
	{
		cin>>x[i]>>g[i]>>d[i];
		ans=max(ans,g[i]);
		g[i]+=g[i-1];
	
	}

	int l=1;
	

	update(1,1,n,n,n,d[n]);

	int lst=x[n];
	for(int i=n-1;i>0;i--)
	{
		update(1,1,n,i+1,n,x[i]-lst);
		update(1,1,n,i,n,d[i]);
		int r=query(1,1,n,i,n);
	
		if(r!=-1)
		   ans=max(ans,g[r]-g[i-1]);
		lst=x[i];
	}
	cout<<ans<<endl;
	return 0;
}

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

divide.cpp: In function 'int query(int, int, int, int, int)':
divide.cpp:12:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=b+e>>1;
          ~^~
divide.cpp: In function 'void update(int, int, int, int, int, long long int)':
divide.cpp:59:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=b+e>>1;
             ~^~
divide.cpp: In function 'int main()':
divide.cpp:84:6: warning: unused variable 'l' [-Wunused-variable]
  int l=1;
      ^

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