Submission #370521

#	Time	Username	Problem	Language	Result	Execution time	Memory
370521		daniel920712	Bigger segments (IZhO19_segments)	C++14	100 / 100	622 ms	52204 KiB

segments

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

using namespace std;
long long all[500005];
pair < long long ,long long > DP[500005];
long long sum[500005]={0},N;
struct A
{
    long long nxl,nxr;
    pair < long long , long long > ans;
    pair < long long , long long > tt;
    long long here;
    long long rnd;
}Node[500005];
long long root=0;
void UPD(long long here)
{
    Node[here].ans=max(Node[Node[here].nxl].ans,Node[Node[here].nxr].ans);
    Node[here].ans=max(Node[here].ans,Node[here].tt);
}
void New(long long here,long long con,pair < long long ,long long > ans)
{
    Node[here].ans=Node[here].tt=ans;
    Node[here].here=con;
    Node[here].nxl=0;
    Node[here].nxr=0;
    Node[here].rnd=rand();
}
pair < long long , long long > split(long long here,long long con)
{
    pair < long long , long long > tt;
    if(here==0) return make_pair(0,0);
    //printf("%lld\n",here);
    if(con>=Node[here].here)
    {
        tt=split(Node[here].nxr,con);
        Node[here].nxr=tt.first;
        tt.first=here;
        UPD(here);
    }
    else
    {
        tt=split(Node[here].nxl,con);
        Node[here].nxl=tt.second;
        tt.second=here;
        UPD(here);
    }
    return tt;
}
long long Merge(long long a,long long b)
{

    if(a==0) return b;
    else if(b==0) return a;
    if(Node[a].here>Node[b].here)
    {
        //printf("%lld %lld\n",Node[a].here,Node[b].here);
        while(1);
    }
    //printf("%lld %lld\n",a,b);
    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;
    }
}
int main()
{
    srand(time(NULL));
    long long i,j,k,ans=0,tt=0;
    scanf("%lld",&N);
    for(i=1;i<=N;i++)
    {
        scanf("%lld",&all[i]);
        sum[i]=all[i]+sum[i-1];
    }

    Node[0].ans=make_pair(-1e18,-1e18);
    Node[0].tt=make_pair(-1e18,-1e18);
    New(N+1,0,make_pair(0,0));
    root=Merge(root,N+1);
    for(i=1;i<=N;i++)
    {
        //printf("aa %lld\n",i);
        pair < long long , long long > aa,bb;
        bb=split(root,sum[i]);
        aa=Node[bb.first].ans;

        //printf("%lld %lld %lld\n",bb.first,aa.first,aa.second);

        DP[i].first=aa.first+1;
        DP[i].second=sum[i]-sum[aa.second];

        New(i,DP[i].second+sum[i],make_pair(DP[i].first,i));

        root=Merge(bb.first,bb.second);

        bb=split(root,DP[i].second+sum[i]);

         root=Merge(Merge(bb.first,i),bb.second);


        tt=max(tt,DP[i].first);
        //printf("%lld %lld\n",DP[i].first,DP[i].second);
    }
    printf("%lld\n",tt);
    return 0;
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:83:17: warning: unused variable 'j' [-Wunused-variable]
   83 |     long long i,j,k,ans=0,tt=0;
      |                 ^
segments.cpp:83:19: warning: unused variable 'k' [-Wunused-variable]
   83 |     long long i,j,k,ans=0,tt=0;
      |                   ^
segments.cpp:83:21: warning: unused variable 'ans' [-Wunused-variable]
   83 |     long long i,j,k,ans=0,tt=0;
      |                     ^~~
segments.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |     scanf("%lld",&N);
      |     ~~~~~^~~~~~~~~~~
segments.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |         scanf("%lld",&all[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27