oj.uz

Submission #1086954

# Submission time Handle Problem Language Result Execution time Memory
1086954 2024-09-11T21:00:04 Z Noname_1900 Wall (IOI14_wall) C++17
100 / 100
 558 ms 110468 KB 
#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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1116 KB Output is correct
5 Correct 3 ms 1188 KB Output is correct
6 Correct 5 ms 1112 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 86 ms 14168 KB Output is correct
3 Correct 134 ms 8528 KB Output is correct
4 Correct 420 ms 22744 KB Output is correct
5 Correct 221 ms 23868 KB Output is correct
6 Correct 215 ms 22292 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 5 ms 1112 KB Output is correct
5 Correct 4 ms 1160 KB Output is correct
6 Correct 5 ms 1168 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 81 ms 14004 KB Output is correct
9 Correct 131 ms 8532 KB Output is correct
10 Correct 393 ms 22856 KB Output is correct
11 Correct 222 ms 24000 KB Output is correct
12 Correct 209 ms 22352 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 97 ms 13892 KB Output is correct
15 Correct 27 ms 2640 KB Output is correct
16 Correct 523 ms 23256 KB Output is correct
17 Correct 216 ms 22608 KB Output is correct
18 Correct 217 ms 22540 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 576 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 5 ms 1116 KB Output is correct
5 Correct 4 ms 1112 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 80 ms 13952 KB Output is correct
9 Correct 131 ms 8640 KB Output is correct
10 Correct 387 ms 22864 KB Output is correct
11 Correct 211 ms 23872 KB Output is correct
12 Correct 204 ms 22272 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 85 ms 13916 KB Output is correct
15 Correct 27 ms 2612 KB Output is correct
16 Correct 521 ms 23124 KB Output is correct
17 Correct 220 ms 22608 KB Output is correct
18 Correct 214 ms 22608 KB Output is correct
19 Correct 540 ms 110176 KB Output is correct
20 Correct 550 ms 107680 KB Output is correct
21 Correct 558 ms 110276 KB Output is correct
22 Correct 532 ms 107984 KB Output is correct
23 Correct 526 ms 107604 KB Output is correct
24 Correct 538 ms 107616 KB Output is correct
25 Correct 530 ms 107588 KB Output is correct
26 Correct 530 ms 110468 KB Output is correct
27 Correct 535 ms 110164 KB Output is correct
28 Correct 525 ms 107720 KB Output is correct
29 Correct 507 ms 107796 KB Output is correct
30 Correct 514 ms 107604 KB Output is correct