oj.uz

Submission #341890

# Submission time Handle Problem Language Result Execution time Memory
341890 2020-12-31T11:46:28 Z katearima Bigger segments (IZhO19_segments) C++14
0 / 100
 1 ms 364 KB 
#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=0; i<n; i++){
        cin>>a[i];
    }
    sums[0]=a[0];
    for(int i=1; i<n; i++){
        sums[i]=a[i]+sums[i-1];
    }
    int sp=0; // starting point of segment
    for(int i=0; i<n; i++){
      while(pq.size()!=0 && pq.top().sum <= sums[i]){
            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;
       pq.push(make_pair(2*sums[i]-sums[sp-1], i+1));
    }
    cout<<ans[n-1]<<endl;
}

Compilation message

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

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -