oj.uz

Submission #146924

# Submission time Handle Problem Language Result Execution time Memory
146924 2019-08-26T16:19:05 Z willi19 Art Exhibition (JOI18_art) C++14
0 / 100
 2 ms 376 KB 
#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 -1000000000000;
    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++)
        cin>>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=-1000000000000;
    for(int i=1;i<n;i++)
        ans=max(ans,query(1,n,1,i+1,n)-val[i]+pic[i].second);
    cout<<ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -