제출 #119867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
119867		Learner99	금 캐기 (IZhO14_divide)	C++14	0 / 100	91 ms	24924 KiB

divide

#include <bits/stdc++.h>

using namespace std;

#define int long long 
#define ll long long
const int N=1e6 + 5;
const int M=3e5 + 5;

ll a[M],b[M];
ll tree[4*N],arr[N],lazy[4*N];
ll x[N], g[N], d[N], gg[N], dd[N];

void build(int node,int start,int end)
{
        if(start==end){
                tree[node]=arr[start];
                return ;
        }
        int mid=(start+end)/2;
        build(2*node+1,start,mid);
        build(2*node+2,1+mid,end);
        tree[node]=max(tree[2*node+1],tree[2*node+2]);
}
void update(int node,int start,int end,int l,int r,ll val)
{
        if(lazy[node]!=0){
                ll foo=lazy[node];
                lazy[node]=0;
                tree[node]+=foo;
                if(start!=end){
                        
                        lazy[2*node+1]+=foo;
                        lazy[2*node+2]+=foo;
                }
        }
        if(end<l || start>r) return ;
        if(start>=l && end<=r){
                tree[node]+=val;
                if(start!=end){
                        
                        lazy[2*node+1]+=val;
                        lazy[2*node+2]+=val;
                }
                return ;
        }
        int mid=(start+end)/2;
        update(2*node+1,start,mid,l,r,val);
        update(2*node+2,1+mid,end,l,r,val);
        tree[node]=max(tree[2*node+1],tree[2*node+2]);
}
ll quer(int node,int start,int end,int l,int r)
{
        if(lazy[node]!=0){
                ll foo=lazy[node];
                lazy[node]=0;
                tree[node]+=foo;
                if(start!=end){
                        
                        lazy[2*node+1]+=foo;
                        lazy[2*node+2]+=foo;
                }
        }
        if(end<l || start>r) return -1e14 ;
        if(start>=l && end<=r){
                return tree[node];
        }
        int mid=(start+end)/2;
        return ( max(quer(2*node+1,start,mid,l,r) ,  quer(2*node+2,1+mid,end,l,r)));
}
ll quer2(int node, int start, int end)
{
        if(lazy[node]!=0){
                ll foo=lazy[node];
                lazy[node]=0;
                tree[node]+=foo;
                if(start!=end){
                        
                        lazy[2*node+1]+=foo;
                        lazy[2*node+2]+=foo;
                }
        }
        if(start==end){
                if(tree[node]>=0)
                        return start;
                else
                        return -1;
        }
        int mid = (start+end)/2;
        ll foo = tree[2*node+1]+lazy[2*node+1];
        ll bar = tree[2*node+2]+lazy[2*node+2];
        if(bar>=0){
                return quer2(2*node+2,mid+1,end);
        }
        else{
                return quer2(2*node+1,start,mid);
        }

}

int32_t main()
{
        ios_base::sync_with_stdio(false);
        int i;
        for(i=0;i<N;i++){
                lazy[i]=0;
                arr[i]=0;
        }
        int n,m;
        cin>>n;


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

        for(i=0;i<n;i++){
                arr[i]=d[i]-x[i];
               // cout<<arr[i]<<" ";
        }
        //cout<<endl;
    
    
        build(0,0,n-1);
        for(int i=0;i<n;i++)
        {
               // cout<<quer(0,0,n-1,i,i)<<endl;
               // cout<<quer2(0,0,n-1)<<endl;
                int x= quer2(0,0,n-1);
                if(x<0)
                        continue;
                int temp= g[x];
                if(i)
                        temp-=g[i-1];
                ans = max(ans, temp);
                if(i!=n-1)
                {
                        int nextd = d[i+1]-d[i];
                        int temp = nextd - dd[i];
                        update(0,0,n-1,i+1,n-1,temp);
                }
                update(0,0,n-1,i,i,-1e12);
        }
    
        cout<<ans<<endl;

    return 0;
}

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

divide.cpp: In function 'long long int quer2(long long int, long long int, long long int)':
divide.cpp:90:12: warning: unused variable 'foo' [-Wunused-variable]
         ll foo = tree[2*node+1]+lazy[2*node+1];
            ^~~
divide.cpp: In function 'int32_t main()':
divide.cpp:109:15: warning: unused variable 'm' [-Wunused-variable]
         int n,m;
               ^

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