Submission #875424

#	Time	Username	Problem	Language	Result	Execution time	Memory
875424		Denkata	Cake 3 (JOI19_cake3)	C++14	0 / 100	1 ms	2396 KiB

cake3

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+3;
ll i,j,p,q,n,m,k,v[maxn],c[maxn];
pair <ll,ll> inp[maxn];
set <ll> vals;
set <ll> :: iterator it;
ll sum = 0;
bool fl = false;
int l,r;
void add(ll val)
{
    if(vals.size()<m-2)
    {
        vals.insert(val);
        sum+=val;
        if(vals.size()==m-2)
            fl = true,it = vals.begin();
        return ;
    }
    if(*it>=val)
        vals.insert(val);//dano ne pravi problemi s it
    if(*it<val)
    {
        sum -= *it;
        sum += val;
        vals.insert(val);
        it++;
    }
}
void rem(ll val)
{
    if(vals.size()<=m-2)
    {
        vals.erase(val);
        sum-=val;
        fl = false;
        return ;
    }
    //dano ne pravi problemi s it
    if(*it>val)
    {
        vals.erase(val);
    }
    if(*it<=val)
    {
        sum -= val;
        it--;
        sum+=*it;
        vals.erase(val);
    }

}
void activate(int ll,int rr)
{
    while(r<rr)
    {
        r++;
        add(v[r]);
    }
    //cout<<l<<" "<<r<<" "<<sum<<endl;
    while(ll<l)
    {
        l--;
        add(v[l]);
    }
    //cout<<l<<" "<<r<<" "<<sum<<endl;
    while(ll>l)
    {
        rem(v[l]);
        l++;
    }
    //cout<<l<<" "<<r<<" "<<sum<<endl;
    while(rr<r)
    {
        rem(v[r]);
        r--;
    }
    //cout<<l<<" "<<r<<" "<<sum<<endl;
    //cout<<fl<<" "<<sum<<endl;
}
ll overall;
void solve(int l,int r,int optl,int optr)
{
    if(r<l)return;
    int mid = (l+r)/2;
    ll ans = -1e18;
    int pos = optl;
    for(int i=optl; i<=min(mid,optr); i++)
    {
        // cout<<i+1<<" "<<mid-1<<" managed :"<<endl;
        ll tek =v[i]+v[mid] - 2*(c[mid] - c[i]);
        if(i+1<=mid-1)activate(i+1,mid-1);
        if(fl)
            tek+=sum;
        else tek-=1e18;
        //   cout<<tek<<endl;
        if(tek>ans)
        {
            pos = i;
            ans = tek;
            overall = max(overall,ans);
        }

    }
    solve(l,mid-1,optl,pos);
    solve(mid+1,r,pos,optr);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(i=1; i<=n; i++)
    {
        cin>>inp[i].second>>inp[i].first;

    }
    //cout<<endl;
    sort(inp+1,inp+n+1);
    for(i=1; i<=n; i++)
    {
        v[i] = inp[i].second;
        c[i] = inp[i].first;
        //  cout<<v[i]<<" "<<c[i]<<endl;
    }
    sum = v[1];
    l=r=1;
    vals.insert(v[1]);
    it = vals.begin();
    solve(1,n,1,n);
    cout<<overall<<endl;
    return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'void add(ll)':
cake3.cpp:14:19: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   14 |     if(vals.size()<m-2)
      |        ~~~~~~~~~~~^~~~
cake3.cpp:18:23: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   18 |         if(vals.size()==m-2)
      |            ~~~~~~~~~~~^~~~~
cake3.cpp: In function 'void rem(ll)':
cake3.cpp:34:19: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   34 |     if(vals.size()<=m-2)
      |        ~~~~~~~~~~~^~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 19
• Subtask 3: 0 / 76