제출 #956094

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
956094		vjudge1	Bigger segments (IZhO19_segments)	C++17	100 / 100	317 ms	38996 KiB

segments

#include <bits/stdc++.h>
#define getbit(i, j) ((i >> j) & 1)
#define maxn 500005
#define name "main"
using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

long long GetRandom(long long l, long long r)
{
    return uniform_int_distribution<long long> (l, r)(rng);
}

int n,a[maxn],dp[maxn];
long long sum[maxn],lazy[maxn*4],mod=-1e16;
pair<long long,long long> st[maxn*4];

void build(int id,int l,int r)
{
    if(l>r) return;
    if(l==r)
    {
        st[id]={mod,l};
        return;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    st[id]={mod,l};
}

void lazy1(int id)
{
    long long val=lazy[id];
    lazy[id]=0;
    st[id*2].first+=val;
    st[id*2+1].first+=val;
    lazy[id*2]+=val;
    lazy[id*2+1]+=val;
}

void tinh(int id,int l,int r,int vt,long long val)
{
    if(l>vt||r<vt) return;
    if(l==r)
    {
        st[id].first=val;
        return;
    }
    lazy1(id);
    int mid=(l+r)/2;
    tinh(id*2,l,mid,vt,val);
    tinh(id*2+1,mid+1,r,vt,val);
    st[id]=st[id*2];
    if(st[id].first<st[id*2+1].first) st[id]=st[id*2+1];
}

void update(int id,int l,int r,int d,int c,long long val)
{
    if(l>c||r<d) return;
    if(l>=d&&r<=c)
    {
        st[id].first+=val;
        lazy[id]+=val;
        return;
    }
    int mid=(l+r)/2;
    lazy1(id);
    update(id*2,l,mid,d,c,val);
    update(id*2+1,mid+1,r,d,c,val);
    st[id]=st[id*2];
    if(st[id].first<st[id*2+1].first) st[id]=st[id*2+1];
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    if(fopen(name".inp","r"))
    {
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        sum[i]=sum[i-1]+a[i];
    }
    int vt=0;
    build(1,1,n);

    for(int i=1;i<=n;i++)
    {
        update(1,1,n,1,i-1,a[i]);
        while(st[1].first>=0)
        {
            int u=st[1].second;
            if(dp[vt]<dp[u]) vt=u;
            else if(dp[vt]==dp[u]) vt=max(vt,u);
            tinh(1,1,n,u,mod);
        }
        dp[i]=dp[vt]+1;
        long long val=sum[i]-sum[vt];
        tinh(1,1,n,i,-val);
    }
    cout<<dp[n];

}

컴파일 시 표준 에러 (stderr) 메시지

segments.cpp: In function 'int main()':
segments.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
segments.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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