Submission #1258531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258531		Noname_1900	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	40 / 100	1096 ms	3396 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int NMAX = 200000;
#define int long long
const int INFINI = 1e17;
int N;
int hauteur[NMAX];
int chang[NMAX];
//int proGrand[2][NMAX]
/*
//lazy
int arbre[NMAX*3];
pair<int, int> debFin[NMAX*3];
int push[NMAX*3];
int construire(int noeud, int deb, int fin)
{
    push[noeud] = 0;
    debFin[noeud] = {deb, fin};
    if(deb == fin-1)
    {
        return arbre[noeud] = chang[noeud];
    }
    int mil = deb+fin;
    mil/=2;
    return arbre[noeud] = min(construire(noeud*2, deb, mil), construire(noeud*2+1, mil, fin));
}
void pousser(int noeud)
{
    int ajout = push[noeud];
    push[noeud] = 0;
    arbre[noeud] += ajout;
    if(debFin[noeud].first != debFin[noeud].second-1)
    {
        push[noeud*2] += ajout;
        push[noeud*2+1]+= ajout;
    }
}
int trouverMin(int noeud, int deb, int fin)
{
    pousser(noeud);
    if((debFin[noeud].first <= deb)&&(debFin[noeud].second >= fin)) return arbre[noeud];
    if((debFin[noeud].first >= fin) || (debFin[noeud].second <= deb))   return INFINI;
    return min(trouverMin(noeud*2, deb, fin), trouverMin(noeud*2+1, deb, fin));
}
int maj(int noeud, int deb, int fin, int ajout)
{
    pousser(noeud);
    if((debFin[noeud].first <= deb)&&(debFin[noeud].second >= fin)){
        push[noeud] += ajout;
        pousser(noeud);
        return arbre[noeud];
    } 
    if((debFin[noeud].first >= fin) || (debFin[noeud].second <= deb))   return arbre[noeud];
    return arbre[noeud] = min(maj(noeud*2, deb, fin, ajout), maj(noeud*2+1, deb, fin, ajout));
}/** */
//map<int, vector<int>> ordre;
int trouvercoutmin(int milieu)
{
    //etape Montee
    int hActu = -1;
    if(milieu != 0)
    {
        for(int i = 0; i < milieu; i++)
        {
            chang[i] = max(hActu+1, hauteur[i]) - hauteur[i];
            hActu = max(hActu+1, hauteur[i]);
        }
    }
    
    hActu = -1;
    if(milieu != N-1)
    {
        for(int i = N-1; i > milieu; i--)
        {
            chang[i] = max(hActu+1, hauteur[i]) - hauteur[i];
            hActu = max(hActu+1, hauteur[i]);
        }
    }
    if(milieu == 0)
    {
        chang[milieu] = max(hauteur[milieu], hauteur[milieu+1]+chang[milieu+1]+1) - hauteur[milieu];
    }
    else if(milieu == N-1)
    {
        chang[milieu] = max(hauteur[milieu], hauteur[milieu-1]+chang[milieu-1]+1) - hauteur[milieu];
    }
    else
    {
        chang[milieu] =  max(hauteur[milieu], max(hauteur[milieu-1]+chang[milieu-1], hauteur[milieu+1]+chang[milieu+1])+1) - hauteur[milieu];
    }
    //construire(1, 0, N);
  //  cout << milieu << endl;
  //  for(int i = 0; i < N; i++)  cout << chang[i] << " ";
  //  cout << endl;
    //veritable
    //*
    int resG = 0;
    int augmentationG = 0;

    for(int i = 0; i <= milieu; i++)
    {

        if(chang[i] >= augmentationG)
        {
            resG += chang[i] - augmentationG;
            augmentationG += chang[i] - augmentationG;
        }
        else
        {
            augmentationG = chang[i];
        }
            
    }
    int resD = 0, augmentationD = 0;
    for(int i = N-1; i >= milieu; i--)
    {
        
        if(chang[i] >= augmentationD)
        {
            resD += chang[i] - augmentationD;
            augmentationD += chang[i] - augmentationD;
        }
        else
        {
            augmentationD =  chang[i];
        }
        //cout << i << " " << resD << endl;
    }
  // cout << milieu << " : " << resG << " " << resD << endl;
    return max(resG, resD);
    /** */
    /*
 //   cout << endl;
    ordre.clear();
    for(int i = 0; i < N; i++)
    {
        ordre[-chang[i]].push_back(i);
    }
    ordre[0].push_back({});
    int derVal = -1;
    set<pair<int, int>> intersG;
    set<pair<int, int>> intersD;
    int repG = 0, repD = 0;
    for(auto a : ordre)
    {
        int val = -a.first;
        auto ajouts = a.second;
        if(derVal == -1)    derVal = val;
        int dif = derVal-val;
        repG += dif * intersG.size();
        repD += dif*intersD.size();
        derVal = val;
     //   cout << val << endl;
        for(int nouv : ajouts)
        {
            auto it = upper_bound(inters.begin(), inters.end(), pair<int, int>(nouv, nouv+1));
            // cout << "jhl" << endl;
            auto itAv = it;
         //    cout << "jhl" << endl;
          //   cout << "jhl" << endl;
            auto itAp = it;
          //   cout << "jhl" << endl;
            pair<int, int> nouvInter = {nouv, nouv+1};
          //  cout << "jhl" << endl;
            if(itAv != inters.begin())
            {
                itAv--;
            //    cout << "jhl" << endl;
                auto av = *itAv;
                if(av.second == nouv)
                {
                    nouvInter.first == av.first;
                    inters.erase(av);
                }
            }
            if(itAp != inters.end())
            {
                auto ap = *itAp;
                if(ap.first == nouv+1)
                {
                    nouvInter.second == ap.second;
                    inters.erase(ap);
                }
            }
            inters.insert(nouvInter);
        }

    }
    return max(repG, repD);
    /** */
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    for(int i = 0; i < N; i++)
    {
        cin >> hauteur[i];
    }    
    /*/
    int deb = 0, fin = N, chang = 1;
    for(int iD = 0; iD < 2; iD++)
    {
        stack<pair<int, int>> gros;
        
        for(int i = deb; i != fin; i+= chang)
        {
            int elem = hauteur[i];
            while((!gros.empty()) && (elem > gros.top().first)) gros.pop();
            if(gros.empty())
            {
                proGrand[iD][i] = i;
            }
            else
                proGrand[iD][i] = gros.top().second;
            
            gros.push({elem, i});
        }
        deb= N-1;
        fin = -1;
        chang = -1;
    }/** */
    if(N == 1)
    {
        cout << 0;
        return 0;
    }
    int meill = INFINI;
    for(int iMil = 0; iMil < N; iMil++)
    {
        int v = trouvercoutmin(iMil);
      //  cout << "rep " << v << endl;
        meill = min(meill,v);
    }
    cout << meill;
}

• Subtask 1: 40 / 40
• Subtask 2: 0 / 60