Submission #584999

#	Time	Username	Problem	Language	Result	Execution time	Memory
584999		mosiashvililuka	Discharging (NOI20_discharging)	C++14	100 / 100	288 ms	107092 KiB

Discharging

#include<bits/stdc++.h>
using namespace std;
const long long N=999999999999999999LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,f[1000009],dp[1000009],K,B,X,z;
deque <pair <long long, long long > > de;
pair <long long, long long> seg[4000009];
deque <pair <long long, pair <long long, long long> > > SEG;
void upd(long long q, long long w, long long rr){
    if(q>w) return;
    if(seg[rr]==make_pair(-1LL,-1LL)){
        SEG.push_back({rr,{seg[rr].first,seg[rr].second}});
        seg[rr]={K,B};
        return;
    }
    long long mid=(q+w)/2;
    if(seg[rr].first*mid+seg[rr].second>K*mid+B){
        SEG.push_back({rr,{seg[rr].first,seg[rr].second}});
        swap(seg[rr].first,K);swap(seg[rr].second,B);
    }
    if(seg[rr].first*q+seg[rr].second>K*q+B){
        upd(q,mid-1,rr*2);
    }else{
        if(seg[rr].first*w+seg[rr].second>K*w+B){
            upd(mid+1,w,rr*2+1);
        }
    }
}
void read(long long q, long long w, long long rr){
    if(q>w) return;
    if(q==w){
        if(seg[rr]!=make_pair(-1LL,-1LL)) z=min(z,seg[rr].first*X+seg[rr].second);
        return;
    }
    long long mid=(q+w)/2;
    if(seg[rr]!=make_pair(-1LL,-1LL)) z=min(z,seg[rr].first*X+seg[rr].second);
    if(X<mid){
        read(q,mid-1,rr*2);
    }
    if(X>mid){
        read(mid+1,w,rr*2+1);
    }
}
void rollback(long long q){
    while(SEG.size()>q){
        seg[SEG.back().first]=SEG.back().second;
        SEG.pop_back();
    }
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a;
    for(i=1; i<=a; i++){
        cin>>f[i];
    }
    for(i=0; i<=a+1; i++) dp[i]=N;
    for(i=0; i<=4000005; i++){
        seg[i]={-1,-1};
    }
    f[a+1]=N;
    dp[a+1]=0;
    de.push_back({a+1,0});
    for(i=a; i>=1; i--){
        while(de.size()>0){
            c=de.back().first;d=de.back().second;
            if(f[c]<=f[i]){
                de.pop_back();
                rollback(d);
            }else{
                break;
            }
        }
        if(de.size()){
            c=de.back().first;d=de.back().second;
            e=SEG.size();
            B=dp[c];K=f[i];
            upd(1,a,1);

            de.push_back({i,e});
        }

        z=N;
        X=a-i+1;
        read(1,a,1);
        dp[i]=z;
    }
    /*for(i=1; i<=a; i++){
        cout<<dp[i]<<" ";
    }
    cout<<"\n";*/
    cout<<dp[1];
    return 0;
}

Compilation message (stderr)

Discharging.cpp: In function 'void rollback(long long int)':
Discharging.cpp:44:21: warning: comparison of integer expressions of different signedness: 'std::deque<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   44 |     while(SEG.size()>q){
      |           ~~~~~~~~~~^~

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 11 / 11
• Subtask 5: 14 / 14
• Subtask 6: 28 / 28