oj.uz

Submission #119878

# Submission time Handle Problem Language Result Execution time Memory
119878 2019-06-22T14:30:17 Z Learner99 Divide and conquer (IZhO14_divide) C++14
100 / 100
 89 ms 24292 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long 
#define ll long long
#define N 1000000
#define M 3000000

ll a[M],b[M];
ll tree[4*N],arr[N],lazy[4*N];
int xx[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 -1e17 ;
        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>>xx[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];
                }
                xx[i]-=xx[0];
        }

        for(i=0;i<n;i++){
                arr[i]=d[i]-xx[i];
        }
    
        build(0,0,n-1);
        for(int i=0;i<n;i++)
        {
                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 = xx[i+1]- xx[i];
                        int temp = nextd - dd[i];
                        //cout<<temp<<endl;
                        update(0,0,n-1,i+1,n-1,temp);
                }
                update(0,0,n-1,i,i,-1e17);
        }
    
        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
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16000 KB Output is correct
2 Correct 14 ms 16000 KB Output is correct
3 Correct 17 ms 15988 KB Output is correct
4 Correct 14 ms 16120 KB Output is correct
5 Correct 14 ms 16000 KB Output is correct
6 Correct 14 ms 16120 KB Output is correct
7 Correct 14 ms 16000 KB Output is correct
8 Correct 14 ms 16128 KB Output is correct
9 Correct 13 ms 16000 KB Output is correct
10 Correct 13 ms 16000 KB Output is correct
11 Correct 13 ms 16000 KB Output is correct
12 Correct 14 ms 16000 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16000 KB Output is correct
2 Correct 14 ms 16128 KB Output is correct
3 Correct 13 ms 15988 KB Output is correct
4 Correct 14 ms 16128 KB Output is correct
5 Correct 15 ms 16076 KB Output is correct
6 Correct 15 ms 16204 KB Output is correct
7 Correct 14 ms 16108 KB Output is correct
8 Correct 15 ms 16184 KB Output is correct
9 Correct 14 ms 16164 KB Output is correct
10 Correct 15 ms 16256 KB Output is correct
11 Correct 17 ms 16504 KB Output is correct
12 Correct 17 ms 16512 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16384 KB Output is correct
2 Correct 19 ms 16640 KB Output is correct
3 Correct 20 ms 16640 KB Output is correct
4 Correct 48 ms 19064 KB Output is correct
5 Correct 49 ms 19064 KB Output is correct
6 Correct 89 ms 21980 KB Output is correct
7 Correct 81 ms 21980 KB Output is correct
8 Correct 81 ms 22008 KB Output is correct
9 Correct 80 ms 22008 KB Output is correct
10 Correct 83 ms 22008 KB Output is correct
11 Correct 85 ms 24184 KB Output is correct
12 Correct 89 ms 24292 KB Output is correct