Submission #290791

#	Time	Username	Problem	Language	Result	Execution time	Memory
290791		PKhing	Bigger segments (IZhO19_segments)	C++14	100 / 100	372 ms	43516 KiB

segments

#include<bits/stdc++.h>
#define ll long long
#define ii pair<ll,ll>
using namespace std;
ll tab[500005];
ll qs[500005];
ll dp[500005];
ll dp2[500005];
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&tab[i]);
        qs[i]=tab[i]+qs[i-1];
    }
    set<ii,greater<ii>> s;
    s.insert(make_pair(0,0));
    for(int i=1;i<=n;i++){
        auto x = s.lower_bound(make_pair(qs[i],1e9));
        ll want = 2*qs[i]-qs[x->second];
        dp[i] = dp[x->second]+1;
        queue<ii> del;
        for(auto i:s){
            if(i.first>=want){
                del.emplace(i);
            }
            else break;
        }
        while(!del.empty()){
            s.erase(del.front());
            del.pop();
        }
        s.insert(make_pair(want,i));
    }
    printf("%lld",dp[n]);

}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   11 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
segments.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |         scanf("%lld",&tab[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~

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