Submission #957150

#	Time	Username	Problem	Language	Result	Execution time	Memory
957150		Requiem	Bigger segments (IZhO19_segments)	C++17	100 / 100	204 ms	21344 KiB

segments

#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define iii pair<int,ii>
#define vii vector<ii>
#define fi first
#define se second
#define endl '\n'
#define show(T) {for (auto x:T) cout<<x<<' ';cout<<endl;}
using namespace std;
const double eps = 0.0000001;
const int mod = 1e9+7;
const int N = 500005;
const int MATRIX_SIZE = 64;
int n,st[4*N],mcd[N],sum[N],dp[N];
void up(int id,int l,int r,int pos,int val){
    if (l>pos||r<pos) return;
    if (l==r){
        st[id]=val;
        return;
    }
    int mid=(l+r)>>1;
    up(id<<1,l,mid,pos,val);
    up(id<<1|1,mid+1,r,pos,val);
    st[id]=min(st[id<<1],st[id<<1|1]);
}
int get(int id,int l,int r,int ct,int cp,int val){
    if (l>cp||r<ct||st[id]>val) return 1e18;
    if (l==r){
        if (st[id]<=val) return l;
        return 1e18;
    }
    int mid=(l+r)>>1;
    int tam=get(id<<1|1,mid+1,r,ct,cp,val);
    if (tam==1e18)
        tam=get(id<<1,l,mid,ct,cp,val);
    return tam;
}
void solve(){
    cin>>n;
    for (int i=1,tam,pos;i<=n;++i){
        cin>>tam;
        mcd[i]=mcd[i-1]+tam;
        pos=get(1,1,n,1,i-1,mcd[i]);
        if (pos==1e18) pos=0;
        sum[i]=mcd[i]-mcd[pos];
        dp[i]=dp[pos]+1;
        // cout<<i<<' '<<pos<<endl;
        up(1,1,n,i,sum[i]+mcd[i]);
    }
    cout<<dp[n];
}
main() {
    // freopen("ok.inp","r",stdin);
    // freopen("ok.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    // cout<<clock()/1000.0;
}

Compilation message (stderr)

segments.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   53 | main() {
      | ^~~~

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