Submission #370498

#	Time	Username	Problem	Language	Result	Execution time	Memory
370498		daniel920712	Bigger segments (IZhO19_segments)	C++14	0 / 100	138 ms	262148 KiB

segments

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

using namespace std;
long long all[500005];
pair < long long ,long long > DP[500005];
long long sum[500005]={0},N;

struct A
{
    long long l,r;
    pair < long long , long long > ans;
    long long nxl,nxr;
}Node[500005*55];
long long now=1;
void New(long long l,long long r,long long here)
{
    Node[here].l=l;
    Node[here].r=r;
    Node[here].nxl=-1;
    Node[here].nxr=-1;
    Node[here].ans=make_pair(-1e18,-1e18);
}
void cha(long long where,long long here,pair < long long ,long long > con)
{
    Node[here].ans=max(Node[here].ans,con);
    if(Node[here].l==where&&Node[here].r==where) return;
    if(where<=(Node[here].l+Node[here].r)/2)
    {
        if(Node[here].nxl==-1)
        {
            Node[here].nxl=now++;
            New(Node[here].l,(Node[here].l+Node[here].r)/2,Node[here].nxl);
        }
        cha(where,Node[here].nxl,con);
    }
    else
    {
        if(Node[here].nxr==-1)
        {
            Node[here].nxr=now++;
            New((Node[here].l+Node[here].r)/2+1,Node[here].r,Node[here].nxr);
        }
        cha(where,Node[here].nxr,con);
    }
}
pair < long long , long long > Find(long long l,long long r,long long here)
{
    if(here==-1) return make_pair(-1e18,-1e18);
    if(Node[here].l==l&&Node[here].r==r) return Node[here].ans;
    if(r<=(Node[here].l+Node[here].r)/2) return Find(l,r,Node[here].nxl);
    else if(l>(Node[here].l+Node[here].r)/2) return Find(l,r,Node[here].nxr);
    else return max(Find(l,(Node[here].l+Node[here].r)/2,Node[here].nxl),Find((Node[here].l+Node[here].r)/2+1,r,Node[here].nxr));
}
int main()
{
    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];
    }

    New(0,1e16,0);
    cha(0,0,make_pair(0,0));
    DP[0]=make_pair(0,0);
    for(i=1;i<=N;i++)
    {
        pair < long long ,long long > aa=Find(0,sum[i],0);

        DP[i].first=aa.first+1;
        DP[i].second=sum[i]-sum[aa.second];
        //printf("%lld %lld %lld\n",i,DP[i].second+sum[i],DP[i].first);
        cha(DP[i].second+sum[i],0,make_pair(DP[i].first,i));

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

Compilation message (stderr)

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

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