Submission #799547

#	Time	Username	Problem	Language	Result	Execution time	Memory
799547		anton	Safety (NOI18_safety)	C++17	66 / 100	2074 ms	2364 KiB

safety

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>


const int MAX_N = 2*1e5;
const int INF = 1e18;
int n, h, A[MAX_N], B[MAX_N], C[MAX_N];
int up_cost[MAX_N], down_cost[MAX_N];
int up_limit[MAX_N], down_limit[MAX_N];

void find_costs(int l, int r){
    for(int i = l; i<r; i++){
        C[i] = B[i]-A[i];
        if(C[i] == 0){
            up_cost[i] = 1;
            down_cost[i] = 1;
            up_limit[i]= INF;
            down_limit[i] = INF;
        }
        else if(C[i]<0){
            up_limit[i] = abs(C[i]);
            down_limit[i] =INF;
            up_cost[i] =-1;
            down_cost[i] =1;
        }
        else if(C[i]>0){
            up_limit[i] = INF;
            down_limit[i] = abs(C[i]);
            up_cost[i] =1;
            down_cost[i] =-1;
        }
    }
}
signed main(){
    cin>>n>>h;

    for(int i = 0; i<n; i++){
        cin>>A[i];
    }
    int res= 0;
    B[0] = A[0];
    C[0] =0;
    up_cost[0] = down_cost[0] = 1;
    vector<pii> oc;
    for(int i = 1; i<n; i++){
        if(abs(A[i]-B[i-1])<=h){
            B[i] = A[i];
            C[i] = 0;
            up_cost[0] = down_cost[0] = 1;
        }
        else{
            int pos = -1;
            int s= 0;
            if(A[i]>B[i-1]){
                ////cout<<"up"<<endl;
                
                int lim = abs(B[i-1] -A[i]);
                oc.clear();
                oc.push_back(pii(i, 0));
                for(int j = i-1; j>=0; j--){
                    s+=up_cost[j];
                    lim = min(lim, up_limit[j]);
                    
                    //cout<<"lim "<<lim<<endl;
                    if(s==0){
                        
                        oc.push_back(pii(j, lim));
                    }
                }
                reverse(oc.begin(), oc.end());
                int move =0;
                for(int inter= 0; inter<oc.size()-1; inter++){
                    int j = oc[inter].first;
                    if(oc[inter].first>0){
                        //cout<<"diff "<<abs(B[j-1]+h-B[j]-move)<<endl;
                        move = min(oc[inter].second, move +abs(B[j-1]+h-B[j]-move));
                    }
                    else{
                        move = oc[inter].second;
                    }
                    
                    //cout<<oc[inter].first<<" "<<move<<endl;
                    for(int j = oc[inter].first; j<oc[inter+1].first; j++){
                        B[j] += move;
                    }
                }
                find_costs(0, i+1);
            }
            else{
                ////cout<<"down"<<endl;
                int lim = abs(B[i-1] -A[i]);
                oc.clear();
                oc.push_back(pii(i, 0));
                for(int j = i-1; j>=0; j--){
                    s+=down_cost[j];
                    lim = min(lim, down_limit[j]);
                    ////cout<<"cost "<<up_cost[j]<<endl;
                    //cout<<"lim "<<lim<<endl;
                    if(s==0){
                        oc.push_back(pii(j,lim));
                    }
                }
                reverse(oc.begin(), oc.end());
                int move =0;
                for(int inter= 0; inter<oc.size()-1; inter++){
                    
                    int j = oc[inter].first;
                    if(oc[inter].first>0){
                        move = min(oc[inter].second, move +abs(B[j-1]-h-B[j]+move));
                    }
                    else{
                        move = oc[inter].second;
                    }
                    //cout<<oc[inter].first<<" "<<move<<endl;
                    for(int j = oc[inter].first; j<oc[inter+1].first; j++){
                        B[j] -= move;
                    }
                }
                find_costs(0, i+1);
                
            }

            if(abs(A[i]-B[i-1])<=h){
                B[i] = A[i];
                C[i] = 0;
                up_cost[0] = down_cost[0] = 1;
            }
            else{
                if(A[i]>B[i-1]){
                    B[i] = B[i-1] +h;
                }
                else{
                    B[i] = B[i-1] -h;
                }
            } 
        }
        find_costs(0, i+1);

        for(int i = 0; i<n; i++){
            //cout<<B[i]<<" ";
        }
        //cout<<endl;
        ////cout<<endl;
    }

    find_costs(0, n);

    for(int i = 0; i<n; i++){
        res+=abs(C[i]);
    }

    for(int i = 0; i<n; i++){
        //cout<<B[i]<<" ";
    }
    //cout<<endl;

    cout<<res<<endl;


}

Compilation message (stderr)

safety.cpp: In function 'int main()':
safety.cpp:75:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |                 for(int inter= 0; inter<oc.size()-1; inter++){
      |                                   ~~~~~^~~~~~~~~~~~
safety.cpp:108:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |                 for(int inter= 0; inter<oc.size()-1; inter++){
      |                                   ~~~~~^~~~~~~~~~~~
safety.cpp:55:17: warning: unused variable 'pos' [-Wunused-variable]
   55 |             int pos = -1;
      |                 ^~~

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 0 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 22 / 22
• Subtask 9: 0 / 29