Submission #1258579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258579		Noname_1900	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++20	100 / 100	15 ms	6532 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int NMAX = 200000+1;
#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;
void initChang()
{
    int milieu = 1;
    int hActu = -1;
    if(milieu != 1)
    {
        for(int i = 1; i < milieu; i++)
        {
            chang[i] = max(hActu+1, hauteur[i]) - hauteur[i];
            hActu = max(hActu+1, hauteur[i]);
        }
    }
    
    hActu = -1;
    if(milieu != N)
    {
        for(int i = N; i > milieu; i--)
        {
            chang[i] = max(hActu+1, hauteur[i]) - hauteur[i];
            hActu = max(hActu+1, hauteur[i]);
        }
    }
    if(milieu == 1)
    {
        chang[milieu] = max(hauteur[milieu], hauteur[milieu+1]+chang[milieu+1]+1) - hauteur[milieu];
    }
    else if(milieu == N)
    {
        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];
    }
}
int resG[NMAX];
int resD[NMAX];
int augmentationG[NMAX+1];
int augmentationD[NMAX+1];
int ancAugG, ancAugD;
void initRes()
{
    int milieu = 1;
    for(int i = 1; i <= 1; i++)
    {
        resG[i] = resG[i-1];
        if(chang[i] >= chang[i-1])
        {
            resG[i] += chang[i] - chang[i-1];
        }
     //   augmentationG[i] = chang[i];
        
            
    }
    for(int i = N; i >= 1; i--)
    {
        resD[i] = resD[i+1];
        if(chang[i] >= chang[i+1])
        {
            resD[i] += chang[i] - chang[i+1];
        }
     //   augmentationD[i] = chang[i];
        //cout << i << " " << resD << endl;
    }
}
void updateChang(int iMilieuNouv)
{
    if(iMilieuNouv == 2)
    {
        chang[iMilieuNouv-1] = 0;
    }
    else
        chang[iMilieuNouv-1] = max(hauteur[iMilieuNouv-2]+chang[iMilieuNouv-2] +1, hauteur[iMilieuNouv-1]) - hauteur[iMilieuNouv-1];

    if(iMilieuNouv == N)
    {
        chang[iMilieuNouv] = max(hauteur[iMilieuNouv], hauteur[iMilieuNouv-1]+chang[iMilieuNouv-1]+1) - hauteur[iMilieuNouv];
    }
    else
    {
        chang[iMilieuNouv] =  max(hauteur[iMilieuNouv], max(hauteur[iMilieuNouv-1]+chang[iMilieuNouv-1], hauteur[iMilieuNouv+1]+chang[iMilieuNouv+1])+1) - hauteur[iMilieuNouv];
    }
    
}
void updateRes(int imilieu)
{
    //TO DO
    if(imilieu > N) return;
    if(imilieu == 2)
    {
        resG[1] = 0;
       // augmentationG[1] = 0;
    }
  //  for(int i = 1; i <= N; i++) cout << chang[i] << " ";
   // cout << endl;
    //augmentationG[imilieu-1] = chang[imilieu-1];
    for(int i = max((long long)2, imilieu-1); i <= imilieu; i++)
    {
        resG[i] = resG[i-1];
        if(chang[i] >= chang[i-1])
        {
            resG[i] += chang[i] - chang[i-1];
          //  cout << i << " " << resG[i] << ' ' << chang[i-1] << " " << chang[i] << endl;
        }
       // augmentationG[i] = chang[i];
    }//*
    if(imilieu == N)    resD[N] = chang[N];
    else
    {
        resD[imilieu] = resD[imilieu+1];
        if(chang[imilieu] >= chang[imilieu+1])
        {
            resD[imilieu] += chang[imilieu] - chang[imilieu+1];
        }
        ///cout << imilieu << " " << resD[imilieu+1] << " " << chang[imilieu] << " " << chang[imilieu+1] << endl;
    }
   // cout << "update " << imilieu << " resG : " << resG[imilieu] << " | rssD : " << resD[imilieu] <<endl;
}
int trouvercoutmin(int milieu)
{
    //etape Montee
    
    //construire(1, 0, N);
  //  cout << milieu << endl;
  //  for(int i = 0; i < N; i++)  cout << chang[i] << " ";
  //  cout << endl;
    //veritable
    //*
    
  // cout << milieu << " : " << resG << " " << resD << endl;
  int a =  max(resG[milieu], resD[milieu]);
    //cout << milieu << " " << resG[milieu] << " " << resD[milieu] << endl;
    updateChang(milieu+1);
    updateRes(milieu+1);
    return a;
    /** */
    /*
 //   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 = 1; 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;
    initChang();
    initRes();
    for(int iMil = 1; iMil <= N; iMil++)
    {
        int v = trouvercoutmin(iMil);
      //  cout << "rep " << v << endl;
        meill = min(meill,v);
    }
    cout << meill;
}

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