Submission #376702

#	Time	Username	Problem	Language	Result	Execution time	Memory
376702		daniel920712	Cake 3 (JOI19_cake3)	C++14	24 / 100	4048 ms	12652 KiB

cake3

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <utility>
#include <time.h>

using namespace std;
pair < long long , long long > all[200005];
long long pre[200005]={0};
//vector < long long > tt;

struct A
{
    long long here;
    long long sum;
    long long rnd;
    long long nxl,nxr;
    long long sz=0;
}Node[200005];
long long root=0;
long long now;
void UPD(long long here)
{
    Node[here].sum=Node[Node[here].nxl].sum+Node[Node[here].nxr].sum+Node[here].here;
    Node[here].sz=Node[Node[here].nxl].sz+Node[Node[here].nxr].sz+1;
}
long long Merge(long long a,long long b)
{
    if(a==0) return b;
    if(b==0) return a;
    if(Node[a].rnd>Node[b].rnd)
    {
        Node[a].nxr=Merge(Node[a].nxr,b);
        UPD(a);
        return a;
    }
    else
    {
        Node[b].nxl=Merge(a,Node[b].nxl);
        UPD(b);
        return b;
    }
}
pair < long long , long long > split1(long long here,long long con)
{
    pair < long long , long long > tt;
    if(here==0) return make_pair(0,0);
    if(Node[here].here>con)
    {
        tt=split1(Node[here].nxl,con);
        Node[here].nxl=tt.second;
        UPD(here);
        tt.second=here;
        return tt;
    }
    else
    {
        tt=split1(Node[here].nxr,con);
        Node[here].nxr=tt.first;
        UPD(here);
        tt.first=here;
        return tt;
    }
}
pair < long long , long long > split2(long long here,long long con)
{
    pair < long long , long long > tt;
    if(here==0) return make_pair(0,0);
    if(Node[Node[here].nxl].sz>=con)
    {
        tt=split2(Node[here].nxl,con);
        Node[here].nxl=tt.second;
        UPD(here);
        tt.second=here;
        return tt;
    }
    else
    {
        tt=split2(Node[here].nxr,con-Node[Node[here].nxl].sz-1);
        Node[here].nxr=tt.first;
        UPD(here);
        tt.first=here;
        return tt;
    }
}
void BFS(long long here)
{
    if(here==0) return ;
    BFS(Node[here].nxl);
    printf("%lld\n",Node[here].here);
    BFS(Node[here].nxr);
}
int main()
{
    srand(time(NULL));
    long long N,M,ans=-1e18,i,j,k,xx=0;
    pair < long long , long long > tt;
    scanf("%lld %lld",&N,&M);
    for(i=1;i<=N;i++)
    {
        scanf("%lld %lld",&all[i].second,&all[i].first);
    }
    sort(all+1,all+N+1);
    for(i=1;i<=N;i++)
    {
        root=0;
        Node[0].here=0;
        Node[0].sum=0;
        Node[0].sz=0;
        for(j=i;j<=N;j++)
        {
            Node[j-i+1].here=all[j].second;
            Node[j-i+1].sz=1;
            Node[j-i+1].nxl=0;
            Node[j-i+1].nxr=0;
            Node[j-i+1].sum=all[j].second;
            Node[j-i+1].rnd=rand();
            tt=split1(root,all[j].second);
            root=Merge(Merge(tt.first,j-i+1),tt.second);
            //printf("aa %lld %lld\n",i,j);
            //BFS(root);
            //printf("\n");
            if(j-i+1>=M)
            {
                xx=0;
                tt=split2(root,j-i+1-M);
                //BFS(tt.second);
                //printf("%lld\n",Node[tt.second].sum);
                xx=Node[tt.second].sum;
                xx-=2*(all[j].first-all[i].first);
                ans=max(ans,xx);
                root=Merge(tt.first,tt.second);
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:98:33: warning: unused variable 'k' [-Wunused-variable]
   98 |     long long N,M,ans=-1e18,i,j,k,xx=0;
      |                                 ^
cake3.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  100 |     scanf("%lld %lld",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
cake3.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |         scanf("%lld %lld",&all[i].second,&all[i].first);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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