Submission #1086954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086954		Noname_1900	Wall (IOI14_wall)	C++17	100 / 100	558 ms	110468 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int NMAX = 2000000;
int arbre[NMAX*3+1];
pair<int, int> debFin[NMAX*3+1];
int aPush[NMAX*3+1][2];
int hFin[NMAX];
#define INFINI 2000000
void tester(int noeud, int deb, int fin)
{
   // cout << noeud << " : " << deb << " " << fin << endl;
  aPush[noeud][0] = 0;
        aPush[noeud][1] = INFINI;
  debFin[noeud] = {deb, fin};
    if(deb == fin-1)  return;
    tester(noeud*2, deb, (deb+fin)/2);
    tester(noeud*2+1, (deb+fin)/2, fin);
}

void chang(int noeud)
{
  if(debFin[noeud].first == debFin[noeud].second-1)
  {
    
    hFin[debFin[noeud].first] = max(aPush[noeud][0], hFin[debFin[noeud].first]);
    hFin[debFin[noeud].first] = min(aPush[noeud][1], hFin[debFin[noeud].first]);
    //cout << "dhkjd" << noeud << endl;
  }
  else
  {
      if(aPush[noeud][0] > aPush[noeud*2][1])
      {
          aPush[noeud*2][1] = aPush[noeud][0];
      }
      if(aPush[noeud][1] < aPush[noeud*2][0])
      {
          aPush[noeud*2][0] = aPush[noeud][1];
      }
      aPush[noeud*2][0] = max(aPush[noeud][0], aPush[noeud*2][0]);
      aPush[noeud*2][1] = min(aPush[noeud][1], aPush[noeud*2][1]);

      if(aPush[noeud][0] > aPush[noeud*2+1][1])
      {
          aPush[noeud*2+1][1] = aPush[noeud][0];
      }
      if(aPush[noeud][1] < aPush[noeud*2+1][0])
      {
          aPush[noeud*2+1][0] = aPush[noeud][1];
      }
      aPush[noeud*2+1][0] = max(aPush[noeud][0], aPush[noeud*2+1][0]);
      aPush[noeud*2+1][1] = min(aPush[noeud][1], aPush[noeud*2+1][1]);

  }
  aPush[noeud][0] = 0;
  aPush[noeud][1] = INFINI;
}
void testerFin(int noeud, int deb, int fin)
{
    
  chang(noeud);
//  cout << noeud << " : " << deb << " " << fin << endl;
    if(deb == fin-1)  return;
    testerFin(noeud*2, deb, (deb+fin)/2);
    testerFin(noeud*2+1, (deb+fin)/2, fin);
}
void adapter(int noeud, int deb, int fin, int op, int h)
{
    chang(noeud);
    if((debFin[noeud].first >= fin) || (debFin[noeud].second <= deb)) return;
  //  cout << noeud << endl;
    if((debFin[noeud].first >= deb) && (debFin[noeud].second <= fin))
    {
        if(op == 0)
        {
            aPush[noeud][0] = max(aPush[noeud][0], h);
            if(aPush[noeud][1] < h)
            {
                aPush[noeud][1] = h;
            }
        }
        else
        {
            aPush[noeud][1] = min(aPush[noeud][1], h);
            if(aPush[noeud][0] > h)
            {
                aPush[noeud][0] = h;
            }
        }
        return;
    }
    adapter(noeud*2, deb, fin, op, h);
    adapter(noeud*2+1, deb, fin, op, h);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  
  tester(1, 0, n);
  for(int i = 0; i < k; i++)
  {
    int opADonner = op[i]-1;
    int debADonner = left[i];
    int finADonner = right[i]+1;
    int hADonner = height[i];
    adapter(1, debADonner, finADonner, opADonner, hADonner);
   /* for(int i = 1; i < 32; i++)
    {
      cout << i << " : ";
        cout << aPush[i][0] << " " << aPush[i][1] << "\n";
    }
    cout << endl;/** */
  }
  testerFin(1, 0, n);
  for(int i = 0; i < n; i++)
  {
      finalHeight[i] = hFin[i];
  }
  return;
}

Compilation message (stderr)

wall.cpp:110:18: warning: "/*" within comment [-Wcomment]
  110 |     cout << endl;/** */
      |

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39