Submission #341900

#	Time	Username	Problem	Language	Result	Execution time	Memory
341900		katearima	Bigger segments (IZhO19_segments)	C++14	100 / 100	252 ms	21972 KiB

segments

#include <bits/stdc++.h>
#define int long long
#define sum  first
#define ind second
using namespace std;
const int N=500005;
int a[N],sums[N], oldS, n;
int ans[N];
priority_queue<pair<int, int> , vector<pair<int, int>> , greater<pair<int, int>>> pq;
main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>a[i];
    }
    sums[1]=a[1];
    for(int i=2; i<=n; i++){
        sums[i]=a[i]+sums[i-1];
    }
    int sp=0; // starting point of segment
    for(int i=1; i<=n; i++){
        //cout<<sums[i]<<endl;
      while(pq.size()!=0 && pq.top().sum <= sums[i]){
            //cout<<pq.top().sum<<" "<<sums[i]<<" "<<pq.top().ind<<" "<<sp<<endl;
            int j=pq.top().ind;
            if(ans[j]>ans[sp]) sp=j;
            else if(ans[j]==ans[sp]) sp=max(j, sp);
            pq.pop();

      }
       ans[i] = ans[sp]+1;
       //cout<<sums[i]<<" "<<sums[sp];
       //cout<<2*sums[i]-sums[sp]<<endl;
       pq.push(make_pair(2*sums[i]-sums[sp], i));
    }
    cout<<ans[n]<<endl;
}

Compilation message (stderr)

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

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