Submission #1187006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187006		inesfi	Just Long Neckties (JOI20_ho_t1)	C++20	100 / 100	85 ms	14256 KiB

ho_t1

#include<bits/stdc++.h>
using namespace std;

#define endl "\n"
#define int long long

const int TAILLEMAXI=(1<<19),DECA=(1<<18);
int rep[DECA];
vector<int> pers;
vector<pair<int,int>> nouv;
int arbre[TAILLEMAXI];

int maxi(int a,int b){
    if (a==b){
        return arbre[a];
    }
    if (a%2==1){
        return max(arbre[a],maxi(a+1,b));
    }
    if (b%2==0){
        return max(arbre[b],maxi(a,b-1));
    }
    return maxi(a/2,b/2);
}

void change(int a){
    while (a>1){
        a/=2;
        arbre[a]=max(arbre[2*a],arbre[2*a+1]);
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int nbpers;
    cin>>nbpers;
    for (int i=0;i<nbpers+1;i++){
        int a;
        cin>>a;
        nouv.push_back({a,i});
    }
    for (int i=0;i<nbpers;i++){
        int b;
        cin>>b;
        pers.push_back(b);
    }
    sort(nouv.begin(),nouv.end());
    sort(pers.begin(),pers.end());
    for (int i=0;i<nbpers;i++){
        arbre[DECA+i]=max(nouv[i+1].first-pers[i],(int)0);
        //cout<<arbre[DECA+]
    }
    for (int i=DECA-1;i>=1;i--){
        arbre[i]=max(arbre[2*i],arbre[2*i+1]);
    }
    rep[nouv[0].second]=maxi(DECA,DECA+nbpers-1);
    /*for (int j=0;j<nbpers;j++){
        cout<<arbre[DECA+j]<<" ";
    }
    cout<<endl;*/
    for (int i=0;i<nbpers;i++){
        arbre[DECA+i]=max(nouv[i].first-pers[i],(int)0);
        change(DECA+i);
        /*for (int j=0;j<nbpers;j++){
            cout<<arbre[DECA+j]<<" ";
        }
        cout<<endl;*/
        rep[nouv[i+1].second]=maxi(DECA,DECA+nbpers-1);
    }
    for (int i=0;i<nbpers+1;i++){
        cout<<rep[i]<<" ";
    }
    cout<<endl;
    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 8 / 8
• Subtask 3: 91 / 91