Submission #146930

#TimeUsernameProblemLanguageResultExecution timeMemory
146930willi19Art Exhibition (JOI18_art)C++14
100 / 100
366 ms33076 KiB
#include <bits/stdc++.h>
using namespace std;
int n;
long long maxt[2000100],ans,val[500100];
pair<long long,long long> pic[500100];
void init(int s,int f,int node)
{
    if(s==f)
    {
        maxt[node]=val[s];
        return;
    }
    init(s,(s+f)/2,node*2);
    init((s+f)/2+1,f,node*2+1);
    maxt[node]=max(maxt[node*2],maxt[node*2+1]);
}
long long query(int s,int f,int node,int l,int r)
{
    if(f<l||r<s)
        return -100000000000000000;
    if(l<=s&&f<=r)
        return maxt[node];
    return max(query(s,(s+f)/2,node*2,l,r),query((s+f)/2+1,f,node*2+1,l,r));
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%lld %lld",&pic[i].first,&pic[i].second);
    sort(pic+1,pic+n+1);
    for(int i=1;i<=n;i++)
        val[i]+=(val[i-1]+pic[i-1].first-pic[i].first+pic[i].second);
    init(1,n,1);
    ans=0;
    for(int i=1;i<n;i++)
    {
        ans=max(ans,query(1,n,1,i,n)-val[i]+pic[i].second);
        //cout<<query(1,n,1,i+1,n)-val[i]+pic[i].second<<"\n";
    }
    cout<<ans;
}

Compilation message (stderr)

art.cpp: In function 'int main()':
art.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld",&pic[i].first,&pic[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...