#include <bits/stdc++.h>
#include "wall.h"
#warning That's not FB, that's my FB
using namespace std;
struct node
{
int mx = 0, mx2 = -1, mn = 0, mn2 = -1;
};
node aint[8000005];
void prop(int nod, int l, int r)
{
if (l == r)
return;
aint[2 * nod].mx = min(aint[2 * nod].mx, aint[nod].mx);
aint[2 * nod].mn = min(aint[2 * nod].mn, aint[nod].mx);
aint[2 * nod].mx = max(aint[2 * nod].mx, aint[nod].mn);
aint[2 * nod].mn = max(aint[2 * nod].mn, aint[nod].mn);
aint[2 * nod + 1].mx = min(aint[2 * nod + 1].mx, aint[nod].mx);
aint[2 * nod + 1].mn = min(aint[2 * nod + 1].mn, aint[nod].mx);
aint[2 * nod + 1].mx = max(aint[2 * nod + 1].mx, aint[nod].mn);
aint[2 * nod + 1].mn = max(aint[2 * nod + 1].mn, aint[nod].mn);
if (aint[2 * nod].mn == aint[2 * nod].mx)
aint[2 * nod].mx2 = aint[2 * nod].mn2 = -1;
else
{
aint[2 * nod].mx2 = max(aint[2 * nod].mx2, aint[nod].mn);
aint[2 * nod].mn2 = min(aint[2 * nod].mn2, aint[nod].mx);
}
if (aint[2 * nod + 1].mn == aint[2 * nod + 1].mx)
aint[2 * nod + 1].mx2 = aint[2 * nod + 1].mn2 = -1;
else
{
aint[2 * nod + 1].mx2 = max(aint[2 * nod + 1].mx2, aint[nod].mn);
aint[2 * nod + 1].mn2 = min(aint[2 * nod + 1].mn2, aint[nod].mx);
}
}
void update(int nod, int l, int r, int st, int dr, int tip, int h)
{
if (r < st or dr < l)
return;
prop(nod,l,r);
if (st <= l and r <= dr)
{
if (tip == 1)
{
if (h <= aint[nod].mn)
return;
if (aint[nod].mn2 == -1 or h < aint[nod].mn2)
{
if (aint[nod].mx2 == aint[nod].mn)
aint[nod].mx2 = h;
//aint[nod].lazy_tag_min = true;
aint[nod].mn = h;
if (aint[nod].mn2 == -1)
{
//aint[nod].lazy_tag_max = true;
aint[nod].mx = h;
}
//cout << "wow" << nod << ' ' << l << ' ' << r << endl;
return;
}
}
else
{
if (h >= aint[nod].mx)
return;
if (aint[nod].mx2 == -1 or h > aint[nod].mx2)
{
if (aint[nod].mn2 == aint[nod].mx)
aint[nod].mn2 = h;
//aint[nod].lazy_tag_max = true;
aint[nod].mx = h;
if (aint[nod].mx2 == -1)
{
//aint[nod].lazy_tag_min = true;
aint[nod].mn = h;
}
return;
}
}
}
//cout << nod << ' ' << l << ' ' << r << endl;
int mij = (l + r) / 2;
update(2 * nod, l, mij, st, dr, tip, h);
update(2 * nod + 1, mij + 1, r, st, dr, tip, h);
vector<int> ele = {aint[2 * nod].mx, aint[2 * nod].mx2, aint[2 * nod].mn, aint[2 * nod].mn2, aint[2 * nod + 1].mx, aint[2 * nod + 1].mx2, aint[2 * nod + 1].mn, aint[2 * nod + 1].mn2};
sort(ele.begin(),ele.end());
vector<int> e2;
for (int i = 0; i < 8; i++)
if ((i == 0 or ele[i] != ele[i - 1]) and ele[i] != -1)
e2.push_back(ele[i]);
if (e2.size() == 1)
{
aint[nod].mx = aint[nod].mn = e2[0];
aint[nod].mx2 = aint[nod].mn2 = -1;
}
else
{
int sz = e2.size();
aint[nod].mx = e2[sz - 1];
aint[nod].mx2 = e2[sz - 2];
aint[nod].mn = e2[0];
aint[nod].mn2 = e2[1];
}
}
int query(int nod, int l, int r, int st, int dr)
{
if (r < st or dr < l)
return 0;
prop(nod,l,r);
if (st <= l and r <= dr)
return aint[nod].mn;
int mij = (l + r) / 2;
return max(query(2 * nod,l,mij,st,dr), query(2 * nod + 1,mij + 1,r,st,dr));
}
void buildWall (int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
for (int i = 0; i < k; i++)
{
left[i]++;
right[i]++;
update(1,1,n,left[i],right[i],op[i],height[i]);
}
for (int i = 0; i < n; i++)
finalHeight[i] = query(1,1,n,i + 1,i + 1);
}
///hai sa vedem daca iese si cu beats :)
Compilation message
Compilation timeout while compiling wall
