Submission #898556

#	Time	Username	Problem	Language	Result	Execution time	Memory
898556		White	Bigger segments (IZhO19_segments)	C++14	0 / 100	1 ms	524 KiB

segments

#pragma GCC optimize <"O3">
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

long long red[500005];

int main(){

    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);

    long long n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>red[i];

    long long L=red[0],br=1,N;
    multiset<long long>cur,clr;

    for(int i=1;i<n;i++){
        long long N=red[i];
        if(N>=L){
            br++;
            L=N;
            cur=clr;
        }else{
            if(cur.empty()){
                cur.insert(N);
            }else{
                auto irr=cur.end();
                --irr;
                long long big=*irr;
                if(big+N<L){
                    cur.insert(big+N);
                }else{
                    auto ir=cur.lower_bound(big-(L-N));
                    long long ss;
                    if(ir==cur.begin())ss=0;
                    else{
                        --ir;
                        ss=*ir;
                    }
                    //cout<<ss<<endl;
                    L=N+big-ss;
                    br++;
                    cur=clr;
                }
            }
        }
    }

    cout<<br<<endl;

    return 0;
}

Compilation message (stderr)

segments.cpp:1:22: warning: '#pragma GCC optimize' is not a string or number [-Wpragmas]
    1 | #pragma GCC optimize <"O3">
      |                      ^
segments.cpp: In function 'int main()':
segments.cpp:17:29: warning: unused variable 'N' [-Wunused-variable]
   17 |     long long L=red[0],br=1,N;
      |                             ^

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