oj.uz

답안 #119867

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
119867 2019-06-22T14:10:09 Z Learner99 금 캐기 (IZhO14_divide) C++14
0 / 100
 91 ms 24924 KB 
#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;
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 16128 KB Output is correct
2 Incorrect 14 ms 16128 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 16000 KB Output is correct
2 Correct 14 ms 16044 KB Output is correct
3 Incorrect 14 ms 16128 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 16512 KB Output is correct
2 Correct 21 ms 16760 KB Output is correct
3 Correct 22 ms 16964 KB Output is correct
4 Correct 50 ms 20132 KB Output is correct
5 Correct 50 ms 20316 KB Output is correct
6 Correct 91 ms 24924 KB Output is correct
7 Correct 86 ms 23928 KB Output is correct
8 Correct 82 ms 23800 KB Output is correct
9 Correct 81 ms 23672 KB Output is correct
10 Incorrect 49 ms 23708 KB Output isn't correct
11 Halted 0 ms 0 KB -