Submission #711270

#	Time	Username	Problem	Language	Result	Execution time	Memory
711270		ToroTN	Bigger segments (IZhO19_segments)	C++14	100 / 100	423 ms	41588 KiB

segments

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define X first
#define Y second
set<pair<ll,ll> > s;
set<pair<ll,ll> > :: iterator it;
vector<pair<ll,ll> > v;
ll n,a,qs[500005],sum[500005],dp[500005],from,cal;
ll query(ll l,ll r)
{
    if(l>r)return 0;
    return qs[r]-qs[l-1];
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a);
        qs[i]=qs[i-1]+a;
        dp[i]=1e18;
    }
    s.insert({0,0});
    for(int i=1;i<=n;i++)
    {
        it=s.upper_bound({qs[i],1e18});
        --it;
        from=(*it).Y;
        dp[i]=dp[from]+1;
        cal=qs[i]+query(from+1,i);
        s.insert({cal,i});
        it=s.upper_bound({cal,i});
        v.clear();
        while(it!=s.end())
        {
            v.pb(*it);
            ++it;
        }
        for(auto [x,y]:v)s.erase({x,y});
        it=s.find({cal,i});
        if(it!=s.begin())
        {
            --it;
            if((*it).X==cal)s.erase(*it);
        }
    }
    printf("%lld\n",dp[n]);
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:41:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |         for(auto [x,y]:v)s.erase({x,y});
      |                  ^
segments.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
segments.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%lld",&a);
      |         ~~~~~^~~~~~~~~~~

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